Computational Complexity Theory

Front Cover
American Mathematical Soc.
0 Reviews
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Selected pages

Contents

History and Basic Concepts
7
Resources Reductions and P vs NP
19
Probabilistic and Quantum Computation
29
Complexity Classes
35
Space Complexity and Circuit Complexity
45
Oracles and the Polynomial Time Hierarchy
55
Circuit Lower Bounds
65
Natural Proofs of Lower Bounds
75
An Introduction to Proof Complexity
201
Lower Bounds in Proof Complexity
215
Automatizability and Interpolation
227
The Restriction Method
233
Other Research and Open Problems
241
RANDOMNESS IN COMPUTATION
247
RANDOMNESS IN COMPUTATION
249
Pseudorandomness Part I
253

Average Case Complexity
89
Average Case Complexity
91
Exploring Complexity through Reductions
101
PCP Theorem and Hardness of Computing Approximate Solutions
105
Which Problems Have Strongly Exponential Complexity?
113
Todas Theorem PH PP
119
Quantum Computation
127
Introduction
129
Bipartite Quantum Systems
139
Quantum Circuits and Shors Factoring Algorithm
147
LOWER BOUNDS
157
Circuit and Communication Complexity
159
Communication Complexity
161
Lower Bounds for Probabilistic Communication Complexity
167
Communication Complexity and Circuit Depth
175
Lower Bound for Directed stConnectivity
185
Lower Bound for FORK Continued
191
Proof Complexity
199
Computational Indistinguishability
257
Pseudorandom Generators
265
Pseudorandom Functions and Concluding Remarks
273
Pseudorandomness Part II
287
Deterministic Simulation of Randomized Algorithms
291
The NisanWigderson Generator
297
Analysis of the NisanWigderson Generator
305
Randomness Extractors
309
Probabilistic Proof Systems Part I
315
Interactive Proofs
317
ZeroKnowledge Proofs
331
Probabilistically Checkable Proofs
349
Introduction to PCPs
351
NPHardness of PCS
361
A Couple of Digressions
369
Proof Composition and the PCP Theorem
379
Copyright

Common terms and phrases

Popular passages

Page xiv - Program and publications documenting the interactive activities which are a primary focus of the PCMI. At the summer institute late afternoons are devoted to seminars of common interest to all participants. Many deal with current issues in education; others...
Page 314 - Theory and applications of trapdoor functions. In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, pages 80-91.
Page 15 - However, such strong reductions appear in other finite problems, for example in the computation of the quadratic residue symbol using repeated application of the law of reciprocity. It would be interesting to know, for instance, the situation concerning the determination of primality of a number and how strongly in general the number of steps in finite combinatorial problems can be reduced with respect to simple exhaustive search. I do not know if you have heard that "Post's problem...
Page xiii - Preface The IAS/Park City Mathematics Institute (PCMI) was founded in 1991 as part of the "Regional Geometry Institute" initiative of the National Science Foundation. In mid 1993 it found an institutional home at the Institute for Advanced Study (IAS) in Princeton. The PCMI will continue to hold summer programs in both Park City and in Princeton.

Bibliographic information