eBook ISBN:  9781470439095 
Product Code:  PCMS/10.E 
List Price:  $112.00 
MAA Member Price:  $100.80 
AMS Member Price:  $89.60 
eBook ISBN:  9781470439095 
Product Code:  PCMS/10.E 
List Price:  $112.00 
MAA Member Price:  $100.80 
AMS Member Price:  $89.60 

Book DetailsIAS/Park City Mathematics SeriesVolume: 10; 2004; 389 ppMSC: Primary 68; Secondary 03
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.
ReadershipGraduate students and research mathematicians interested in computational complexity.

Table of Contents

Chapters

Introduction

Week One: Complexity theory: From Gödel to Feynman

Complexity theory: From Gödel to Feynman

Average case complexity

Exploring complexity through reductions

Quantum computation

Week Two: Lower Bounds

Circuit and Communication Complexity

Proof complexity

Week Three: Randomness in computation

Preface to “Week Three: Randomness in Computation”

Pseudorandomness—Part I

Pseudorandomness—Part II

Probabilistic proof systems—Part I

Probabilistically checkable proofs


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


RequestsReview Copy – for publishers of book reviewsAccessibility – to request an alternate format of an AMS title
 Book Details
 Table of Contents
 Reviews
 Requests
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.
Graduate students and research mathematicians interested in computational complexity.

Chapters

Introduction

Week One: Complexity theory: From Gödel to Feynman

Complexity theory: From Gödel to Feynman

Average case complexity

Exploring complexity through reductions

Quantum computation

Week Two: Lower Bounds

Circuit and Communication Complexity

Proof complexity

Week Three: Randomness in computation

Preface to “Week Three: Randomness in Computation”

Pseudorandomness—Part I

Pseudorandomness—Part II

Probabilistic proof systems—Part I

Probabilistically checkable proofs

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