Date

Topic

Readings

Notes

Homework

Sep 6
Course logistics; Turing machines.
Sec 3.1 of TC
Chapter 1 and Sec 2.1 of CC


Sep 8
Multitape Turing machines; Simulation of multitape
Turing machines by single-tape Turing machines;
Diagonalization; Undecidability of the halting problem.
Sec 3.2 and 4.2 of TC
Sec 2.2, 2.3, 3.1 and 3.2 of CC
Note 1
HW 1
Sep 13
Time and space complexity; P, EXPTIME, L and
PSPACE; Linear speedup; PSPACE is in EXPTIME;
and the Space hierarchy theorem.
Sec 7.1, 7.2 and 9.1 of TC
Sec 2.4, 2.5, 7.1 and 7.2 of CC


Sep 15
Universal Turing machines; Time hierarchy;
Nondeterministic Turing machines.
Sec 7.3 and 9.1 of TC
Sec 3.1, 7.2 and 2.7 of CC


Sep 20
NP and co-NP; NP and verifiers; PSPACE and
recursion; Generalized Geography is in PSPACE.
Sec 7.3 and 8.2 of TC
Sec 7.1 of CC


Sep 22
Savitch's theorem; PSPACE = NPSPACE;
NL = coNL.
Sec 8.1, 8.2 and 8.6 of TC
Sec 7.3 of CC

Set 1 due
Sep 27
Karp reduction and NP-completeness; Reduction
from 3SAT to Clique; NP-completeness of SAT.
Sec 7.4 of TC
Sec 8.1, 8.2 and Chapter 9 of CC


Sep 29
NP-completeness of Vertex cover, Hamiltonian
path, and Subset-sum.
Sec 7.5 of TC
Chapter 9 of CC

HW 2
Oct 4
Ladner's theorem;
PSPACE-completeness of TQBF.
Sec 8.3 of TC
Sec 19.1 of CC


Oct 6
PSPACE-completeness of Generalized Geography;
the Polynomial Hierarchy; consequence of P = NP.
Sec 8.3 of TC
Sec 17.2 of CC


Oct 11
Oracle Turing machines; \Sigma_2^P = NP^{SAT}.
Sec 9.2 and 10.3 of TC
Sec 14.3 of CC


Oct 13
Boolean circuits; Circuit-SAT; and P/poly.
Sec 9.3 of TC
Sec 4.1 of LC

Set 2 due
Oct 18
P/poly vs sparse sets; Karp–Lipton theorem.
Sec 4.2 of LC


Oct 20
In-class Midterm



Oct 25
Mahaney's theorem; Basic probability;
a randomized algorithm for MAXCUT.
Sec 4.3 of LC
Sec 5.2.2 of LC


Oct 27
Markov inequality; Variance and Chebyshev
inequalities; Chernoff bound; Randomized
complexity classes; Amplification of RP and BPP.
Sec 5.1.1, 5.1.2, 5.1.3
and Sec 5.4 of LC


Nov 1
BPP is in \Sigma_2^P; Universal hashing;Isolation lemma.
Sec 5.5, Sec 5.1.4,
and Sec 5.6 of LC


Nov 3
Approximate Counting and Unique Satisfiability.
Sec 5.8 and 5.9 of LC

HW 3
Nov 8
Academic holiday



Nov 10
Interactive proof systems.
Sec 10.4 of TC


Nov 15
#SAT is in IP.
Sec 10.4 of TC


Nov 17
IP = PSPACE.
Sec 10.4 of TC

Set 3 due
Nov 22
PCP theorem
Chapter 11 of MA


Nov 24
Thanksgiving Day -- University holiday


HW 4
Nov 29
Circuit lower bound:
Razborov-Smolensky Theorem
Sec 11.2 of LC


Dec 1
Razborov-Smolensky Theorem (Cont.);
Switching Lemma
Sec 11.3 of LC



Dec 6
Switching Lemma (Cont.)
Sec 11.3 of LC


Dec 8
More topics (We will have the final in the registrar
assigned slot of 12/22/2016 between 7:10 and 10pm.)


HW 4 due on Dec 13







CC: Computational Complexity
TC: Introduction to the Theory of Computation
MA: Computational Complexity: A Morden Approach
LC: Lectures in Computational Complexity (by Jin-Yi Cai)