Preface |
Committees |
Ron Book Prize for Best Student Paper |
Time-Space Tradeoff Lower Bounds for Non-Uniform Computation / P. Beame |
Time-Space Tradeoffs for Nondeterministic Computation / L. Fortnow ; D. van Melkebeek |
A Lower Bound for the Shortest Path Problem / K. Mulmuley ; P. Shah |
Time-Space Lower Bounds for SAT on Uniform and Non-Uniform Machines / I. Tourlakis |
BP (f) = O (L (f)[superscript 1+varepsilon]) / O. Giel |
The Communication Complexity of Enumeration, Elimination, and Selection / A. Ambainis ; H. Buhrman ; W. Gasarch ; B. Kalyanasundaram ; L. Torenvliet |
The Query Complexity of Order-Finding / R. Cleve |
On the Complexity of Some Problems on Groups Input as Multiplication Tables / D. Barrington ; P. Kadau ; K-J. Lange ; P. McKenzie |
The Complexity of Tensor Calculus / C. Damm ; M. Holzer |
The Complexity of Verifying the Characteristic Polynomial and Testing Similarity / T. Hoang ; T. Thierauf |
A Dual Version of Reimer's Inequality and a Proof of Rudich's Conjecture / J. Kahn ; M. Saks ; C. Smyth |
Computational Complexity and Phase Transitions / G. Istrate |
An Application of Matroid Theory to the SAT Problem / O. Kullmann |
New Bounds for the Language Compression Problem / S. Laplante ; P. Miltersen |
Combinatorial Interpretation of Kolmogorov Complexity / A. Romashchenko ; A. Shen ; N. Vereshchagin |
Independent Minimum Length Programs to Translate between Given Strings / N. Vereschagin ; M. Vyugin |
A Survey of Optimal PCP Characterizations of NP / L. Trevisan |
Easiness Assumptions and Hardness Tests: Trading Time for Zero Error / V. Kabanets |
Dimension in Complexity Classes / J. Lutz |
Average Case Complexity of Unbounded Fanin Circuits / A. Jakoby ; R. Reischuk |
On the Hardness of 4-Coloring a 3-Colorable Graph / V. Guruswami ; S. Khanna |
Deciding the K-Dimension is PSPACE-Complete / M. Schaefer |
Integer Circuit Evaluation is PSPACE-Complete / K. Yang |
A Separation of Determinism, Las Vegas and Nondeterminism for Picture Recognition / P. Duris ; J. Hromkovic ; K. Inoue |
On the Complexity of Intersecting Finite State Automata / G. Karakostas ; R. Lipton ; A. Viglas |
On the Complexity of the Monotonicity Verification / A. Voronenko |
What Complexity and Cryptography Can Teach Each Other / R. Impagliazzo |
Quantum Kolmogorov Complexity / A. Berthiaume ; W. van Dam |
On the Complexity of Quantum ACC / F. Green ; S. Homer ; C. Pollett |
Three Approaches to the Quantitative Definition of Information in an Individual Pure Quantum State / P. Vitanyi |
Characterization of Non-Deterministic Quantum Query and Quantum Communication Complexity / R. de Wolf |
Author Index |
Preface |
Committees |
Ron Book Prize for Best Student Paper |