## Computational Complexity Theory |

### What people are saying - Write a review

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

### 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 |

### Common terms and phrases

accepts apply approximation Boolean circuits Boolean function circuit lower bounds classical clauses co-NP coloring communication complexity complexity classes computationally indistinguishable Computer Science constraints construct decision tree define Definition denote depth deterministic distribution edge efficient encoding ensembles example exists exponential formula fraction Frege function f gate given Goldreich graph hard Hence hierarchy input integer interactive proofs interpolation lecture Lemma length linear low-degree matrix MAX-3SAT monotone natural proof node NP-complete NP-hard obtain one-way functions Open Problem oracle output path PCP Theorem pigeonhole principle Player poly log Polynomial Calculus polynomial-time probabilistic algorithm probability at least proof system protocol prove pseudorandom function PSPACE quantum circuit queries query complexity random string rectangle reduction resolution proof restriction result satisfying assignments sequence simulation space tautology Turing machine uniformly variables vector verifier vertex vertices zero zero-knowledge proofs

### 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.