To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.
You may also visit the AMS Bookstore and order directly from there. DIMACS does not distribute or sell these books.
I wish to express my gratitude to my co-organizers and to those of all the other workshops, to Andrew Yao who organized the special year, to the DIMACS Executive Committee for sponsoring these events, and to the participants everywhere for making the special year successful and this volume possible.
The papers published here are a cross section of various research topics currently being explored. They range from circuit complexity and structural complexity to combinatorial analysis, from cryptography to algorithmic game theory. All the papers are final versions. They all have been read by referees, whose comments have usually resulted in substantial revisions, corrections, and improvements. I wish to thank our contributing authors and referees collectively for a job well done. I would also like to thank Winnie Waring for assisting me throughout the refereeing process.
Forward ix Preface xi Approximate Counting with Uniform Constant-Depth Circuits Miklos Ajtai 1 On Strong Separations from AC Eric Allender and Vivek Gore 21 Parallel Matching Complexity of Ramsey's Theorem 39 On Algorithms for Simple Stochastic Games Anne Condon 51 Locally Random Reductions in Interactive Complexity Theory Joan Feigenbaum 73 An Application of Game-Theoretic Techniques to Cryptography Michael J. Fischer and Rebecca N. Wright 99 Composition of the Universal Relation Johan Hastad and Avi Wigderson 119 Practical Perfect Cryptographic Security Ueli M. Maurer 135 Fair Games against an All-Powerful Adversary Rafail Ostrovsky, Ramarathnam Venkatesan, and Moti Yung 155 Factoring Integers and Computing Discrete Logarithms via Diophantine Approximation C.P. Schnorr 171 A New Lower Bound Theorem for Read-Only-Once Branching Programs and its Applications Janos Simon and Mario Szegedy 183 On the E-Isomorphism Problem Jie Wang 195