CMSC 38130 -- Complexity Theory


Instructor

Janos Simon
337 Crerar Library
email: simon (at) cs (dot)uchicago (dot) edu

Lectures:
MW 3:00--4:20 Ry 277


Recommended Text: S. Arora and B. Barak: Computational Complexity: A Modern Approach
Cambridge U Press 2009.

Other Useful/interesting Sources M. Sipser: Introduction to the Theory of Computation 3rd Edition
The Reisch-Schnitger paper for the exam Three_applications_of_Kolmogorov-complexity.pdf
A cute speculative paper on NP-completeness (just for fun)
NP_complete_Problems_and_Physical_Realit-1.pdf

My plan for grading is to base it on homework assignments, and a take-home final.

Course Overview

I will try to cover quickly the main topics of the first 9 chapters of the text, assuming some familiarity with topics like NP-completeness and undecidability. The speed will depend on the students. I will omit many of the more advanced parts of these chapters.

I will the try to cover the PCP theorem.

Material Covered

We have been looking at Computability Theory, which is only barely covered in our text.
I will produce some notes.
9/27 The relevant sections of the text is Chapter 1.

We are going to cover chapters 3 and 4 next, except we are starting with Chapter 4.

9/29 Lecture 2: Universal Turing Machine. Undecidability. Reductions.
10/4 Lecture 3: Languages that cannot be accepted by Turing Machines (c.e.) Enumerators. More undecidability.
10/6 Lecture 4: Logical Formulas and Turing machines. Complexity Classes
10/11 Lecture 5: Space and Time Hierarchies
10/13 Lecture 6: Complete Problems: L, NL, P, NP, coNP, PSPACE
10/18 Lecture 7: Complete Problems for PSPACE. TQBF. Alternating quantifiers as games.
Generalized Geography. A nice overview of GG is in Wikipedia. The proof is stolen from Sipser pg 346-348,
but it has some generalizations.
10/20 Lecture 8. Immerman-Szelepcsényi Theorem NL=coNL. Padding arguments. Baker-Gill-Solovay Theorem. 10/25 Lecture 9. The Polynomial Hierarchy PH. Complete problems at finite levels of the PH. Circuits:
circuit families, size, depth. DTIME[T] has O(T logT) circuit family. Nonuniform Turing machines, P/poly.
10/27 Lecture 10: Two theorems about citcuits:
(Karp-Lipton) $NP\subseteq P_{poly}$ implies PH collapses ($\Sigma^p_2 = \Pi^p_2$)
(Shanon) Most boolean circuits require exponential size circuits.
Probabilistic Turing Machines. PP,BPP, RP coRP. Complete problems for PP
Sketch of improving precision. $RP\subseteq P_{poly}$
11/1 Lecture 11: Precise statement on BPP precision improvement (Theorem 7.10) using Chernoff bounds.
$BPP\subseteq \Sigma^p_2 \cup \Pi^p_2$. $BPP \subseteq P_{/poly}$
11/3 Lecture 12. Review of solutions to Problem Set 2.
More about BPP: proof of $BPP \in PH$. Syntactic vs. semantic classes (no complete
problems known). ZPP. Randomized reductions. Pairwise independent hash functions.
USAT. $SL \subseteq BPL$
11/8 Lecture 13 Interactive proofs. Definitions. Examples of protocols: different socks, quadratic nonresidue, graph nonisomorphism. Arthur-Merlin games. Making error probability small.
Equivalence of public and provate coin models (we only saw the proof of graph non-isomorphism).
Wlog prover in PSPACE.
11/10 Lecture 14.Set lower bound protocol. Sumcheck protocol: #$SAT_D \in IP$.
Arithmetization.$ TQBF\in PSPACE$ ($IP=PSPACE$). Definition of the permanent.
11/15 Lecture 15 (actually 11/16). Introduction to PCP and approximation algorithms.
The two views of the PCP theorem:

  1. There are efficient locally samplable proofs for NP
  2. There are constraint satisfaction problems with no arbitrarily good constant factor approximation algorithms

Precise statements for the above.
11/17 Lecture 16 Walsh-Hadamard code and its basic properties.
An easy version of the PCP Theorem, using the Walsh-Hadamard code: NP is contained in PCP(poly(n),1)

In the textbook

See here for a map of what we saw in the Arora and Barak text.

Problem Sets

Final

Final exam here