**IAS/Park City Mathematics Series**

Volume: 10;
2004;
389 pp;
Hardcover

MSC: Primary 68;
Secondary 03

Print ISBN: 978-0-8218-2872-4

Product Code: PCMS/10

List Price: $80.00

Individual Member Price: $64.00

**Electronic ISBN: 978-1-4704-3909-5
Product Code: PCMS/10.E**

List Price: $80.00

Individual Member Price: $64.00

#### You may also like

# Computational Complexity Theory

Share this page *Edited by *
*Steven Rudich; Avi Wigderson*

A co-publication of the AMS and IAS/Park City Mathematics Institute

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.

#### Readership

Graduate students and research mathematicians interested in computational complexity.

#### Reviews & Endorsements

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

## Computational Complexity Theory

- Cover Cover11
- Title page iii4
- Contents v6
- Preface xiii14
- Introduction 116
- Week One: Complexity theory: From Gödel to Feynman 318
- Complexity theory: From Gödel to Feynman 520
- Average case complexity 89104
- Exploring complexity through reductions 101116
- Quantum computation 127142
- Week Two: Lower Bounds 157172
- Circuit and Communication Complexity 159174
- Proof complexity 199214
- Week Three: Randomness in computation 247262
- Preface to “Week Three: Randomness in Computation” 249264
- Pseudorandomness—Part I 253268
- Pseudorandomness—Part II 287302
- Probabilistic proof systems—Part I 315330
- Probabilistically checkable proofs 349364
- Back Cover Back Cover1407