| Mar 6
Turing machine model of computation [AB 1];
Time hierarchy theorem [AB 3.1];
Oracle machines [AB 3.5].
Circuits [AB 6.1]
|| Mar 6
| Mar 13
Space complexity [AB 4, S 8];
stCON is space(log^2n) [AB 4.2.1];
Logspace Reductions, Composition in L [AB 4, S 8.1];
CVAL is P-complete under log-space reductions [6.7.2]
|| Mar 13
Simulating Muli-tape Turing machine by a single tape Turing machine with quadratic time overhead.
||TQBF is PSPACE-complete [AB 4.3];
NP [AB 2.5];
CSAT and 3SAT are NP-complete [S 7.4];
||Boolean CircuitsOracle Machines
||3NAE, 3COL, Clique, IS, VC and Setcover are NPC.
NSpace.NL. [AB 4.3, S 8.1];
STCON is in NL. [AB 4.4];
STCON is in coNL.
||Equivallence of 2 definitions of NP;
Question on unary NPC language.
The polynomial time hierarchy.
Pratt certificates for primality (See...)
Defined RP, BPP
||Separation with Diagonalization
||Amplification of BPP algorithms, Chernoff bound.
Schwartz-zippel lemma. (See...)
A probabilistic algorithm for Matching in a bi-partite graph.
Polynomial identity testing.
||The polynomial time hierarchy.
|| Karger's min-cut algorithm - primality testing with a probabilistic algorithm (Fermat, Euler, Rabin-Miller (no proof)).
2 Definitions of NL.
2SAT is in NL.
|| Communication complexity.
The log-rank lower bound.
An exponential gap between the deterministic and probabilistic communication complexity of the EQ function.
Schoning's algorithm for 3SAT.
The Karp-Lipton theorem.
Search vs DecisionGriddy Derandomization Algorithm.
||BPP in Sigma_2
2-approximation 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 de-randomizing the probabilistic proof.
||Amplifications of BPP.If SAT is in BPP then SAT is in RP.
||Public coins, MA, AM, IP.
GNISO is in AM.
MA in AM,
if GISO is NP-complete the hierarchy collapses.
AM in Pi_2.
IP in PSPACE.
||#SAT is #P-Complete.
||#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]
||The PCP theorem.
The PCP theorem implies Gap Max3SAT is NP-hard.
Hardness of approximation.
Gap preserving reductions.
Max-clique is NP-hard to approximate up to some constant.
An amplified PCP theorem.
Max-clique is NP-hard to approximate up to n^alpha for some constant alpha.
||Hardness of approximating VC.
The importance of the gap location.
Gp max 3SAT(b) (using expanders).
Error correcting codes and the Hadamard code.
||SubsetSum is NPC but Gap-SubsetSum[1-e,1] is easy for any e<1.
NOT FOR EXAM.
2-Local decoding of the Hadamard code.
Linearity testing of the Hadamard code (with analysis using Fourier transform).
QuadEQ is NP-complete. QuadEq in PCP(poly(n),O(1)).
||Lecture 15 NOT FOR EXAM