Graduate Computational Complexity Theory

This introductory lecture surveys the fundamental scope and methodologies of graduate computational complexity theory, referencing core concepts from Arora-Barak Chapters 1, 2, and 4.

This session delves into the Hierarchy Theorems, establishing distinct complexity classes based on time, space, and nondeterministic resource bounds as detailed in Arora-Barak.

Focuses on the Hopcroft Paul Valiant Theorem, examining its implications for efficient simulation of multi-tape Turing machines by single-tape machines.

Explores the theory of Boolean circuits as a model of computation, including definitions, size, depth, and connections to complexity classes, drawing from Arora-Barak.

This lecture introduces fundamental probabilistic complexity classes such as RP, coRP, ZPP, and BPP, analyzing their definitions and interrelationships using randomized algorithms.

Examines the Quasilinear Cook-Levin Theorem, focusing on its construction and the reduction of any problem in NP to SAT in quasilinear time.

Investigates the Polynomial Time Hierarchy (PH), defining its levels _kP and _kP through oracle Turing machines and alternating quantifiers.

Explores the role of oracles in complexity theory and contrasts the Polynomial Time Hierarchy with the capabilities of bounded-depth circuits.

Analyzes fundamental time-space tradeoffs for solving the Satisfiability problem, exploring different computational models and their resource requirements.

Introduces the Arthur-Merlin (AM) and Merlin-Arthur (MA) complexity classes, formalizing interactive proof systems with probabilistic verifiers.

Expands on constant-round interactive proof systems, demonstrating their power and limitations in recognizing languages efficiently with probabilistic interaction.

Addresses the problem of approximate counting for computationally hard problems, discussing techniques for estimating the size of solution sets within polynomial time.

Presents the Valiant-Vazirani Theorem, establishing a connection between NP and randomized exact counting (#P), providing insights into counting complexity.

This lecture introduces Toda's First Theorem, demonstrating that the Polynomial Time Hierarchy is contained within P^#P, and discusses the complexity of computing the Permanent.

A detailed proof establishes that computing the Permanent of a matrix is a #P-complete problem, underscoring its significant computational hardness.

Explores algebraic circuit complexity, analyzing the computation of polynomials over various fields using algebraic circuits and related lower bound techniques.

Examines instance checking techniques in the context of the Permanent problem, exploring methods to verify specific computations efficiently.

Demonstrates the seminal result that the class of languages with Interactive Proof systems (IP) is precisely equivalent to Polynomial Space (PSPACE).