This collection of recent papers on computational complexity theory grew out of activities during a special year at DIMACS. With contributions by some of the leading experts in the field, this book is of lasting value in this fast-moving field, providing expositions not found elsewhere. Although aimed primarily at researchers in complexity theory and graduate students in mathematics or computer science, the book is accessible to anyone with an undergraduate education in mathematics or computer science. By touching on some of the major topics in complexity theory, this book sheds light on this burgeoning area of research.

Co-published with the Center for Discrete Mathematics and Theoretical Computer Science beginning with Volume 8. Volumes 1-7 were co-published with the Association for Computer Machinery (ACM).

Readership

Researchers in complexity theory and graduate students in computer science or mathematics with interests in computation.

Table of Contents

• M. Ajtai -- Approximate counting with uniform constant-depth circuits
• E. Allender and V. Gore -- On strong separations from $AC^0$
• J. Beck -- Parallel matching complexity of Ramsey's theorem
• A. Condon -- On algorithms for simple stochastic games
• J. Feigenbaum -- Locally random reductions in interactive complexity theory
• M. J. Fischer and R. N. Wright -- An application of game-theoretic techniques to cryptography
• J. Hå stad and A. Wigderson -- Composition of the universal relation
• U. M. Maurer -- Practical perfect cryptographic security
• R. Ostrovsky, R. Venkatesan, and M. Yung -- Fair games against an all-powerful adversary
• C. P. Schnorr -- Factoring integers and computing discrete logarithms via diophantine approximation
• J. Simon and M. Szegedy -- A new lower bound theorem for read-only-once branching programs and its applications
• J. Wang -- On the E -isomorphism problem