Computational Complexity TheoryAmerican Mathematical Soc. |
Contents
| 7 | |
| 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 |
Other editions - View all
Common terms and phrases
accepts algorithm allows answer apply approximation argument assignment assume bits Boolean called circuit classical clauses coloring communication complexity computation consider constant constraints construct contains corresponding define Definition denote depth deterministic distinguisher distribution edge efficient example exists fact Figure formula fraction function gate give given graph hard Hence input instance interactive proofs language least lecture Lemma length linear lower bound machine matrix MAX-3SAT measure monotone natural Note obtain oracle output particular path Player polynomial possible probabilistic probability problem Proof Complexity proof system protocol prove pseudorandom quantum quantum circuit queries random reduction requires resolution restriction result running satisfies simulation solve space steps string Suppose Theorem Theory tree Turing uniform variables vector verifier vertices zero zero-knowledge
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.