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 copublished 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. Readership Graduate students and research mathematicians interested in computational complexity. Reviews "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
 PseudorandomnessPart II
 Introduction
 Deterministic simulation of randomized algorithms
 The NisanWigderson generator
 Analysis of the NisanWigderson generator
 Randomness extractors
 Bibliography
 Probabilistic proof systemsPart I
 Interactive proofs
 Zeroknowledge proofs
 Suggestions for further reading
 Bibliography
 Probabilistically checkable proofs
 Introduction to PCPs
 NPhardness of PCS
 A couple of digressions
 Proof composition and the PCP theorem
 Bibliography
