DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

VOLUME THIRTEEN
TITLE: "ADVANCES IN COMPUTATIONAL COMPLEXITY THEORY"
EDITORS: Jin-Yi Cai
Published by the American Mathematical Society

Ordering Information

This volume may be obtained from the AMS or through bookstores in your area.

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.

PREFACE

During the 1990-1991 academic year DIMACS, the NSF Science and Technology Center in Discrete Mathematics and Theoretical Computer Science, organized a special year in computational complexity theory. The year was a great success, as many researchers from all over the world gathered at the four institutions comprising DIMACS (Rutgers University, Princeton University, AT & T Bell Laboratories, and Bellcore) and exchanged ideas, created new ones, and presented their work. There were several workshops held throughout the year. One of these, directed by Eric Allender, Joan Feigenbaum, and myself (December 3-7, 1990), concentrated on structural complexity theory and applications to cryptography. This volume represents a selection of the papers presented at this workshop and during the special year.

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.

TABLE OF CONTENTS



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
Index Index of Volumes
DIMACS Homepage
Contacting the Center
Document last modified on October 28, 1998.