New Titles  |  FAQ  |  Keep Informed  |  Review Cart  |  Contact Us Quick Search (Advanced Search ) Browse by Subject General Interest Logic & Foundations Number Theory Algebra & Algebraic Geometry Discrete Math & Combinatorics Analysis Differential Equations Geometry & Topology Probability & Statistics Applications Mathematical Physics Math Education

Edited by: Jin-Yi Cai
A co-publication of the AMS and DIMACS.
 SEARCH THIS BOOK:
DIMACS: Series in Discrete Mathematics and Theoretical Computer Science
1993; 209 pp; hardcover
Volume: 13
ISBN-10: 0-8218-6597-8
ISBN-13: 978-0-8218-6597-2
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 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).

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

• 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