Hardcover ISBN:  9780821865972 
Product Code:  DIMACS/13 
List Price:  $121.00 
MAA Member Price:  $108.90 
AMS Member Price:  $96.80 
eBook ISBN:  9781470439712 
Product Code:  DIMACS/13.E 
List Price:  $114.00 
MAA Member Price:  $102.60 
AMS Member Price:  $91.20 
Hardcover ISBN:  9780821865972 
eBook: ISBN:  9781470439712 
Product Code:  DIMACS/13.B 
List Price:  $235.00 $178.00 
MAA Member Price:  $211.50 $160.20 
AMS Member Price:  $188.00 $142.40 
Hardcover ISBN:  9780821865972 
Product Code:  DIMACS/13 
List Price:  $121.00 
MAA Member Price:  $108.90 
AMS Member Price:  $96.80 
eBook ISBN:  9781470439712 
Product Code:  DIMACS/13.E 
List Price:  $114.00 
MAA Member Price:  $102.60 
AMS Member Price:  $91.20 
Hardcover ISBN:  9780821865972 
eBook ISBN:  9781470439712 
Product Code:  DIMACS/13.B 
List Price:  $235.00 $178.00 
MAA Member Price:  $211.50 $160.20 
AMS Member Price:  $188.00 $142.40 

Book DetailsDIMACS  Series in Discrete Mathematics and Theoretical Computer ScienceVolume: 13; 1993; 209 ppMSC: Primary 68; Secondary 05
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 1–7 were copublished with the Association for Computer Machinery (ACM).
ReadershipResearchers in complexity theory and graduate students in computer science or mathematics with interests in computation.

Table of Contents

Chapters

Approximate counting with uniform constant depth circuits

On strong separations from $AC^0$

Parallel matching complexity of Ramsey’s theorem

On algorithms for simple stochastic games

Locally random reductions in interactive complexity theory

An application of game theoretic techniques to cryptography

Composition of the universal relation

Practical perfect cryptographic security

Fair games against an allpowerful adversary

Factoring integers and computing discrete logarithms via diophantine approximation

A new lower bound theorem for read only once branching programs and its applications

On the Eisomorphism problem


RequestsReview Copy – for publishers of book reviewsAccessibility – to request an alternate format of an AMS title
 Book Details
 Table of Contents
 Requests
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 1–7 were copublished with the Association for Computer Machinery (ACM).
Researchers in complexity theory and graduate students in computer science or mathematics with interests in computation.

Chapters

Approximate counting with uniform constant depth circuits

On strong separations from $AC^0$

Parallel matching complexity of Ramsey’s theorem

On algorithms for simple stochastic games

Locally random reductions in interactive complexity theory

An application of game theoretic techniques to cryptography

Composition of the universal relation

Practical perfect cryptographic security

Fair games against an allpowerful adversary

Factoring integers and computing discrete logarithms via diophantine approximation

A new lower bound theorem for read only once branching programs and its applications

On the Eisomorphism problem