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
Monday, February 18, 2008
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment