AMS Bookstore LOGO amslogo
Return to List  Item: 1 of 1   
Computational Complexity Theory
Edited by: Steven Rudich, Carnegie Mellon University, Pittsburgh, PA, and Avi Wigderson, Institute for Advanced Study, Princeton, NJ
A co-publication of the AMS and IAS/Park City Mathematics Institute.

IAS/Park City Mathematics Series
2004; 389 pp; hardcover
Volume: 10
ISBN-10: 0-8218-2872-X
ISBN-13: 978-0-8218-2872-4
List Price: US$80
Member Price: US$64
Order Code: PCMS/10
[Add Item]

Request Permissions

See also:

A Primer on Pseudorandom Generators - Oded Goldreich

Computational Complexity Theory is the study of how much of a given resource is required to perform the computations that interest us the most. Four decades of fruitful research have produced a rich and subtle theory of the relationship between different resource measures and problems. At the core of the theory are some of the most alluring open problems in mathematics.

This book presents three weeks of lectures from the IAS/Park City Mathematics Institute Summer School on computational complexity. The first week gives a general introduction to the field, including descriptions of the basic models, techniques, results and open problems. The second week focuses on lower bounds in concrete models. The final week looks at randomness in computation, with discussions of different notions of pseudorandomness, interactive proof systems and zero knowledge, and probabilistically checkable proofs (PCPs). It is recommended for independent study by graduate students or researchers interested in computational complexity.

The volume is recommended for independent study and is suitable for graduate students and researchers interested in computational complexity.

Titles in this series are co-published with the Institute for Advanced Study/Park City Mathematics Institute. Members of the Mathematical Association of America (MAA) and the National Council of Teachers of Mathematics (NCTM) receive a 20% discount from list price.


Graduate students and research mathematicians interested in computational complexity.


"This book contains well written accounts of many branches of complexity theory. ... In particular, any CS grad student doing theory, or any math grad student, should be able to read this book. ... This book would be a good way to learn a lot of complexity theory quickly."

-- Mathematical Reviews

Table of Contents

  • Week One: Complexity theory: From Gödel to Feynman
  • Complexity theory: From Gödel to Feynman
  • History and basic concepts
  • Resources, reductions and P vs. NP
  • Probabilistic and quantum computation
  • Complexity classes
  • Space complexity and circuit complexity
  • Oracles and the polynomial time hierarchy
  • Circuit lower bounds
  • "Natural" proofs of lower bounds
  • Bibliography
  • Average case complexity
  • Average case complexity
  • Bibliography
  • Exploring complexity through reductions
  • Introduction
  • PCP theorem and hardness of computing approximate solutions
  • Which problems have strongly exponential complexity?
  • Toda's theorem: \(PH \subseteq P^{\#P}\)
  • Bibliography
  • Quantum computation
  • Introduction
  • Bipartite quantum systems
  • Quantum circuits and Shor's factoring algorithm
  • Bibliography
Lower bounds
  • Circuit and communication complexity
  • Communication complexity
  • Lower bounds for probabilistic communication complexity
  • Communication complexity and circuit depth
  • Lower bound for directed \(st\)-connectivity
  • Lower bound for \(FORK\) (continued)
  • Bibliography
  • Proof complexity
  • An introduction to proof complexity
  • Lower bounds in proof complexity
  • Automatizability and interpolation
  • The restriction method
  • Other research and open problems
  • Bibliography
  • Randomness in computation
  • Pseudorandomness
  • Preface
  • Computational indistinguishability
  • Pseudorandom generators
  • Pseudorandom functions and concluding remarks
  • Appendix
  • Bibliography
  • Pseudorandomness-Part II
  • Introduction
  • Deterministic simulation of randomized algorithms
  • The Nisan-Wigderson generator
  • Analysis of the Nisan-Wigderson generator
  • Randomness extractors
  • Bibliography
  • Probabilistic proof systems-Part I
  • Interactive proofs
  • Zero-knowledge proofs
  • Suggestions for further reading
  • Bibliography
  • Probabilistically checkable proofs
  • Introduction to PCPs
  • NP-hardness of PCS
  • A couple of digressions
  • Proof composition and the PCP theorem
  • Bibliography
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