Monday, February 18, 2008

CCC 2008 accepted papers

The list of accepted papers for the computational complexity conference was announced last week. From a quick look through the list i picked these 4 for the top of my papers-to-read stack:

NP-hard sets are exponentially dense unless coNP is contained in NP/poly
Harry Buhrman and John M. Hitchcock

Amplifying Lower Bounds by Means of Self-Reducibility
Eric Allender and Michal Koucký

Lower Bounds and Separations for Constant Depth Multilinear Circuits
Ran Raz and Amir Yehudayoff

Constraint Logic: A Uniform Framework for Modeling Computation as Games
Erik D. Demaine and Robert A. Hearn

No comments:

Post a Comment