Special Issue “Conference on Computational Complexity 2005” Guest Editor’s Foreword
Anna Gál · Computational Complexity · 2006
Preliminary versions of these papers appeared in the conference proceedings.The papers were selected by the Program Committee of the conference, chaired by Luca Trevisan.All papers were refereed according to the journal's standards.This is the second part of the Special Issue; three papers already appeared in the first part, in issue 2 of volume 15.The four papers here include interesting results in the areas of time-space tradeoffs, multiparty communication complexity, derandomization and algebraic complexity.The three papers in the first part represent exciting developments in the areas of hardness of approximation, lower bound methods on classical and quantum computation, and connections between complexity theory and cryptography.This part contains the two award-winning papers of the conference: the 2005 Ronald V. Book Prize for Best Student Paper was given to Ryan Williams for his paper "Better Time-Space Lower Bounds for SAT and Related Problems", and the 2005 Best Paper Award was given to Ronen