Overview

Computational complexity theory is a major research area in mathematics and computer science, the goal of which is to set the formal mathematical foundations for efficient computation. There has been significant development in the nature and scope of the field in the last thirty years. It has evolved to encompass a broad variety of computational tasks by a diverse set of computational models, such as randomized, interactive, distributed, and parallel computations. These models can include many computers, which may behave cooperatively or adversarially. Each summer the IAS/Park City Mathematics Institute Graduate Summer School gathers some of the best researchers and educators in the field to present diverse sets of lectures. This volume presents three weeks of lectures given at the Summer School on Computational Complexity Theory. Topics are structured as follows: Week One: Complexity Theory: From Godel to Feynman. This section of the book gives a general introduction to the field, with the main set of lectures describing basic models, techniques, results, and open problems. Week Two: Lower Bounds on Concrete Models. Topics discussed in this section include communication and circuit complexity, arithmetic and algebraic complexity, and proof complexity. Week Three: Randomness in Computation. Lectures are devoted to different notions of pseudorandomness, interactive proof systems and zero knowledge, and probabilistically checkable proofs (PCPs). The volume is recommended for independent study and is suitable for graduate students and researchers interested in computational complexity. Information for our distributors: Members of the Mathematical Association of America (MAA) and the National Council of Teachers of Mathematics (NCTM) receive a 20 per cent discount from list price.

Full Product Details

9780821828724

Table of Contents

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

“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

oThis book contains well written accounts of many branches of complexity theory. aIn particular, any CS grad student doing theory, or any math grad student, should be able to read this book. aThis book would be a good way to learn a lot of complexity theory quickly.o -- Mathematical Reviews

Author Information

Tab Content 6

Customer Reviews

Recent Reviews

Countries Available