| Hardcover ISBN: | 978-0-8218-6597-2 |
| Product Code: | DIMACS/13 |
| List Price: | $121.00 |
| MAA Member Price: | $108.90 |
| AMS Member Price: | $96.80 |
| eBook ISBN: | 978-1-4704-3971-2 |
| Product Code: | DIMACS/13.E |
| List Price: | $114.00 |
| MAA Member Price: | $102.60 |
| AMS Member Price: | $91.20 |
| Hardcover ISBN: | 978-0-8218-6597-2 |
| eBook: ISBN: | 978-1-4704-3971-2 |
| 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: | 978-0-8218-6597-2 |
| Product Code: | DIMACS/13 |
| List Price: | $121.00 |
| MAA Member Price: | $108.90 |
| AMS Member Price: | $96.80 |
| eBook ISBN: | 978-1-4704-3971-2 |
| Product Code: | DIMACS/13.E |
| List Price: | $114.00 |
| MAA Member Price: | $102.60 |
| AMS Member Price: | $91.20 |
| Hardcover ISBN: | 978-0-8218-6597-2 |
| eBook ISBN: | 978-1-4704-3971-2 |
| 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 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).
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 all-powerful 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 E-isomorphism 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 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.
-
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 all-powerful 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 E-isomorphism problem
