AMS Bookstore LOGO amslogo
Return to List  Item: 1 of 1   
Advances in Computational Complexity Theory
Edited by: Jin-Yi Cai
A co-publication of the AMS and DIMACS.

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$108
Member Price: US$86.40
Order Code: DIMACS/13
[Add Item]

Request Permissions

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.

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
Powered by MathJax
Return to List  Item: 1 of 1   

  AMS Home | Comments:
© Copyright 2014, American Mathematical Society
Privacy Statement

AMS Social

AMS and Social Media LinkedIn Facebook Podcasts Twitter YouTube RSS Feeds Blogs Wikipedia