| Dedication |
| Preface |
| Conference Organization |
| Best Paper Award |
| Ron Book Prize for Best Student Paper |
| In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time / R. Impagliazzo ; V. Kabanets ; A. WigdersonSession 1： |
| Towards Uniform AC[superscript 0]-Ismorphisms / M. Agrawal |
| Universal Traversal Sequences with Backtracking / M. Koucky |
| Comparing Notions of Full Derandomization / L. Fortnow |
| Monotone Simulations of Nonmonotone Proofs / A. Atserias ; N. Galesi ; P. PudlakSession 2： |
| Space Complexity of Random Formulae in Resolution / E. Ben-Sasson |
| Resolution Complexity of Independent Sets in Random Graphs / P. Beame ; A. Sabharwal |
| Tree Resolution Proofs of the Weak Pigeon-Hole Principle / S. Dantchev ; S. Riis |
| Separation of NP-Completeness Notions / A. Pavan ; A. SelmanSession 3： |
| Bounded Query Functions with Limited Output Bits / R. Chang ; J. Squire |
| A Linear Lower Bound on the Unbounded Error Probabilistic Communication Complexity / J. ForsterSession 4： |
| Towards Proving Strong Direct Product Theorems / R. Shaltiel |
| Communication Complexity Lower Bounds by Polynomials / H. Buhrman ; R. de WolfSession 5： |
| Quantum Algorithms for Element Distinctness / C. Durr ; M. Heiligman ; P. Hoyer ; F. Magniez ; M. Santha |
| Quantum versus Classical Learnability / R. Servedio ; S. Gortler |
| Uniform Circuits for Division: Consequences and Problems / E. Allender ; D. Barrington ; W. HesseSession 6： |
| Affine Projections of Symmetric Polynomials / A. Shpilka |
| On the Non-Approximability of Boolean Functions by OBDDs and Read-K-Times Branching Programs / B. Bollig ; M. Sauerhoff ; I. Wegener |
| Lower Bounds for Approximations by Low Degree Polynomials Over Zm / N. Alon ; R. Beigel |
| On the Power of Nonlinear Secret-Sharing / A. Beimel ; Y. Ishai |
| A Stronger Kolmogorov Zero-One Law for Resource-Bounded Measure / J. DaiSession 7： |
| Hausdorff Dimension in Exponential Time / K. Ambos-Spies ; W. Merkle ; J. Reimann ; F. Stephan |
| On the Complexity of Approximating the VC Dimension / E. Mossel ; C. UmansSession 8： |
| Links Between Complexity Theory and Constrained Block Coding / L. Stockmeyer ; D. Modha |
| Simple Analysis of Graph Tests for Linearity and PCP / J. Hastad |
| Logical Operations and Kolmogorov Complexity II / A. Muchnik ; N. VereshchaginSession 9： |
| Computational Depth / L. Antunes ; D. van Melkebeek |
| Quantum Algorithmic Entropy / P. Gacs |
| On Separators, Segregators and Time versus Space / R. SanthanamSession 10： |
| Time-Space Tradeoffs in the Counting Hierarchy / D. Ronneburger ; S. Roy ; V. Vinay |
| Author Index |
| Dedication |
| Preface |
| Conference Organization |
| Best Paper Award |
| Ron Book Prize for Best Student Paper |
| In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time / R. Impagliazzo ; V. Kabanets ; A. WigdersonSession 1： |
