| Preface |
| Committees |
| Awards |
| ECCC 10th Anniversary |
| Compression of Samplable Sources / L. Trevisan ; S. Vadhan ; D. ZuckermanSession 1： |
| Language Compression and Pseudorandom Generators / H. Buhrman ; T. Lee ; D. van Melkebeek |
| On Pseudoentropy versus Compressibility / H. Wee |
| Reductions between Disjoint NP-Pairs / C. Glasser ; A. Selman ; S. SenguptaSession 2： |
| Relativized NP Search Problems and Propositional Proof Systems / J. Buresh-Oppenheim ; T. Morioka |
| The Complexity of Treelike Systems over [lambda]-Local Formulae / N. Galesi ; N. Thapen |
| Lower Bounds for Testing Bipartiteness in Dense Graphs / A. BogdanovSession 3： |
| Polylogarithmic-round Interactive Proofs for coNP Collapse the Exponential Hierarchy |
| Solvable Group Isomorphism is (almost) in NP [intersection of] CoNP / V. Arvind ; J. Toran |
| Small Spans in Scaled Dimension / J. Hitchcock |
| Computing in Fault Tolerance Broadcast Networks / I. NewmanSession 4： |
| Some Results on Majority Quantifiers over Words / K.-J. Lange |
| Separating Complexity Classes Using Structural Properties / L. Torenvliet |
| Parameterized Complexity of Constraint Satisfaction Problems / D. MarxSession 5： |
| Tight Lower Bounds for Certain Parameterized NP-Hard Problems / J. Chen ; B. Chor ; M. Fellows ; X. Huang ; D. Juedes ; I. Kanj ; G. Xia |
| The Complexity of the Covering Radius Problem on Lattices and Codes / V. Guruswami ; D. Micciancio ; O. Regev |
| Dimension, Entropy Rates, and Compression / N. VinodchandranSession 6： |
| Properties of NP-Complete Sets / A. Pavan |
| Partial Bi-immunity and NP-Completeness |
| Abelian Permutation Group Problems and Logspace Counting Classes / T. VijayaraghavanSession 7： |
| Deterministic Polynomial Identity Testing in Non-commutative Models / R. Raz ; A. Shpilka |
| Polynomials That Sign Represent Parity and Descartes Rule of Signs / S. Basu ; N. Bhatnagar ; P. Gopalan ; R. Lipton |
| Consequences and Limits of Nonlocal Strategies / R. Cleve ; P. Hoyer ; B. Toner ; J. WatrousSession 8： |
| Multiparty Quantum Coin Flipping / A. Ambainis ; Y. Dodis ; H. Rohrig |
| On the Power of Quantum Proofs |
| Quantum Arthur-Merlin Games / C. Marriott |
| Graph Properties and Circular Functions: How Low Can Quantum Query Complexity Go? / X. Sun ; A. Yao ; S. ZhangSession 9： |
| Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments / S. Laplante ; F. Magniez |
| Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information / K. Yang |
| Limitations of Quantum Advice and One-Way Communication / S. Aaronson |
| Author Index |
| Preface |
| Committees |
| Awards |
| ECCC 10th Anniversary |
| Compression of Samplable Sources / L. Trevisan ; S. Vadhan ; D. ZuckermanSession 1： |
| Language Compression and Pseudorandom Generators / H. Buhrman ; T. Lee ; D. van Melkebeek |
