Preface (pdf)
Complexity of computations and proofs
Edited by Jan Krajíček
- Generating Hard Instances
of Lattice Problems
Miklós Ajtai - Arithmetic Circuits and
Counting Complexity Classes
Eric Allender - Variations by complexity
theorists on three themes of Euler, Bèzout, Betti and Poincaré
Peter Bürgisser and Felipe Cucker - Bounded Arithmetic and
Constant Depth Frege Proofs
Stephen Cook - Kolmogorov Complexity and
Computational Complexity
Lance Fortnow - Zero-Knowlegde twenty
years after its invention
Oded Goldreich - Homomorphic public-key
cryptosystems over groups and rings
Dima Grigoriev and Ilia Ponomarenko - Pseudorandom sets and
explicit constructions of Ramsey graphs
Pavel Pudlák and Vojtěch Rödl - Some Applications of
Coding Theory in Computational Complexity
Luca Trevisan