DIMACS: Series in Discrete Mathematics and Theoretical Computer Science 1993; 209 pp; hardcover Volume: 13 ISBN10: 0821865978 ISBN13: 9780821865972 List Price: US$102 Member Price: US$81.60 Order Code: DIMACS/13
 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 fastmoving 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. Copublished with the Center for Discrete Mathematics and Theoretical Computer Science beginning with Volume 8. Volumes 17 were copublished 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 constantdepth 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 gametheoretic 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 allpowerful adversary
 C. P. Schnorr  Factoring integers and computing discrete logarithms via diophantine approximation
 J. Simon and M. Szegedy  A new lower bound theorem for readonlyonce branching programs and its applications
 J. Wang  On the E isomorphism problem
