Item Successfully Added to Cart
An error was encountered while trying to add the item to the cart. Please try again.
OK
Please make all selections above before adding to cart
OK
The following link can be shared to navigate to this page. You can select the link to copy or click the 'Copy To Clipboard' button below.
Copy To Clipboard
Successfully Copied!
Computational Complexity Theory
 
Edited by: Steven Rudich Carnegie Mellon University, Pittsburgh, PA
Avi Wigderson Institute for Advanced Study, Princeton, NJ
A co-publication of the AMS and IAS/Park City Mathematics Institute
Front Cover for Computational Complexity Theory
Available Formats:
Electronic ISBN: 978-1-4704-3909-5
Product Code: PCMS/10.E
List Price: $80.00
MAA Member Price: $72.00
AMS Member Price: $64.00
Front Cover for Computational Complexity Theory
Click above image for expanded view
  • Front Cover for Computational Complexity Theory
  • Back Cover for Computational Complexity Theory
Computational Complexity Theory
Edited by: Steven Rudich Carnegie Mellon University, Pittsburgh, PA
Avi Wigderson Institute for Advanced Study, Princeton, NJ
A co-publication of the AMS and IAS/Park City Mathematics Institute
Available Formats:
Electronic ISBN:  978-1-4704-3909-5
Product Code:  PCMS/10.E
List Price: $80.00
MAA Member Price: $72.00
AMS Member Price: $64.00
  • Book Details
     
     
    IAS/Park City Mathematics Series
    Volume: 102004; 389 pp
    MSC: 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.

    Readership

    Graduate 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
  • Request Review Copy
Volume: 102004; 389 pp
MSC: 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.

Readership

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
You may be interested in...
Please select which format for which you are requesting permissions.