Date 
Class Topic 
Notes 
Date 
Recitation Topic 
Notes 
Mar 6 
Administration;
Turing machine model of computation [AB 1];
Time hierarchy theorem [AB 3.1];
Oracle machines [AB 3.5].
Circuits [AB 6.1]

Lecture 1 
Mar 6 
Strike
Complexity Functions
Turing Machines
 Recitaion 1 
Mar 13 
Space complexity [AB 4, S 8];
L, PSPACE.
stCON is space(log^2n) [AB 4.2.1];
Logspace Reductions, Composition in L [AB 4, S 8.1];
CVAL is Pcomplete under logspace reductions [6.7.2]

Lecture 2 
Mar 13 
Strike
Simulating Mulitape Turing machine by a single tape Turing machine with quadratic time overhead.
 Recitaion 2 
Mar 20 
TQBF is PSPACEcomplete [AB 4.3];
NP [AB 2.5];
CSAT and 3SAT are NPcomplete [S 7.4]; 
Lecture 3 
Mar 20 
Boolean CircuitsOracle Machines 
Recitaion 3 
Mar 27 
3NAE, 3COL, Clique, IS, VC and Setcover are NPC.
coNP.
NSpace.NL. [AB 4.3, S 8.1];
STCON is in NL. [AB 4.4];
STCON is in coNL. 
Lecture 4 
Mar 27 
Equivallence of 2 definitions of NP;
Karp Reduction;
Question on unary NPC language. 
Recitaion 4 
Apr 3 
Zeroerror NL,
NL=coNL.
The polynomial time hierarchy.
Pratt certificates for primality (See...)
Defined RP, BPP

Lecture 5 
Apr 3 
Separation with Diagonalization
Padding Argument 
Recitaion 5 
Apr 17 
Amplification of BPP algorithms, Chernoff bound.
Schwartzzippel lemma. (See...)
A probabilistic algorithm for Matching in a bipartite graph.
Polynomial identity testing.
 Lecture 6 
Apr 17 
The polynomial time hierarchy.

Recitaion 6 
Apr 24 
Karger's mincut algorithm  primality testing with a probabilistic algorithm (Fermat, Euler, RabinMiller (no proof)).
 Lecture 7 
Apr 24 
2 Definitions of NL.
2SAT is in NL.

Recitaion 7 
May 1 
Communication complexity.
The logrank lower bound.
An exponential gap between the deterministic and probabilistic communication complexity of the EQ function.
Schoning's algorithm for 3SAT.
 Lecture 8 
May 1 
Small Examples 
Recitaion 8 
May 8 
Quiz
The KarpLipton theorem. 
Lecture 9 
May 8 
Self Reducibility
Search vs DecisionGriddy Derandomization Algorithm.
 Recitaion 9 
May 15 
BPP in Sigma_2
Approximation algorithms.
2approximation for VC, ln(n) approximation for SetCover.
Every graph has a cut with at least E/2 edges.
Pairwise independent distributions (def+construction).
A deterministic algorithm for a large cut by derandomizing the probabilistic proof. 
Lecture 10 
May 15 
Amplifications of BPP.If SAT is in BPP then SAT is in RP.
 Recitaion 10 
May 22 
Public coins, MA, AM, IP.
GNISO is in AM.
MA in AM,
if GISO is NPcomplete the hierarchy collapses.
AM in Pi_2.
IP in PSPACE. 
Lecture 11 
May 22 
#SAT is #PComplete. 
Recitaion 11 
May 29 
#3SAT in IP. [AB 8.3]
Sketch of PSPACE=IP. [P 19.2]
If PSPACE has polynomial size circuits then PSPACE=MA.[AB 8.4]
Defined PCP(r(n),q(n)).[AB DEF. 11.4]

Lecture 12 
May 29 
Approximating TSP 
Recitaion 12 
Jun 5 
The PCP theorem.
The PCP theorem implies Gap Max3SAT is NPhard.
Hardness of approximation.
Gap preserving reductions.
Maxclique is NPhard to approximate up to some constant.
An amplified PCP theorem.
Maxclique is NPhard to approximate up to n^alpha for some constant alpha. 
Lecture 13 
Jun 5 
PCP 
Recitaion 13 
Jun 12 
Hardness of approximating VC.
The importance of the gap location.
Gp max 3SAT(b) (using expanders).
Error correcting codes and the Hadamard code.
 Lecture 14 
Jun 12 
SubsetSum is NPC but GapSubsetSum[1e,1] is easy for any e<1. 
Recitaion 14 
Jun 19 
NOT FOR EXAM.
2Local decoding of the Hadamard code.
Linearity testing of the Hadamard code (with analysis using Fourier transform).
QuadEQ is NPcomplete. QuadEq in PCP(poly(n),O(1)). 
Lecture 15 NOT FOR EXAM 
Jun 19 
Examples  Recitaion 15 