Computational Complexity Theory
This book is devoted to modern topics in complexity theory. It contains lectures given during the three-week summer school organized by IAS/Park City Mathematics Institute in 2000. The lectures were given by ten leading researchers in complexity theory. Computational power of machines with limited resources is the central notion of this area. The book describes a significant development of this area during the last thirty years. The results lead to a fundamentally new and important way of understanding many central notions beyond computation itself, e.g. proof, knowledge, randomness, cryptography, etc.
The book is divided into three parts; the first part (the first week of the school) contains lectures given by S. Rudich, A. Wigderson, S. Arora and R. Raz. It contains a survey of basic models, techniques, results and open problems (given by S. Rudich), a survey of average-case complexity (given by A. Wigderson), reduction techniques (given by S. Arora) and quantum computation (given by R. Raz). The second part (the second week) is formed from lectures by R. Raz concerning communication and circuit complexity and by P. Beame concerning proof complexity. The last part (the third week) is devoted to randomness in computation. Lectures were given on pseudorandomness by O. Goldreich and L. Trevisan, on interactive proof systems and zero-knowledge by S. Vadhan and on probable checkability proofs by M. Sudan. This interesting book serves students and researchers of the complexity theory and also students and researchers in adjacent fields using computation tools.