SYLLABUS
Fundamentals.
- Turing machine- Non-deterministic time
- Time/Space Hierarchy
- Space complexity
- Counting complexity classes
- Randomization
- Circuits
- Interaction
Advanced Topic ideas.
- you choose a paper/result- Matiyasevich's proof of Hilbert's 10th problem
- Reingold's graph reachability in logspace
- AKS' primality test
- Hastad's parity is not in AC_0
- Williams' NEXP is not in ACC_0
- Razborov-Rudich's natural proof barrier
- Aaronson-Wigderson's algebrization barrier
Schedule.
[10-Apr-2014] [pdf] Randomized reductions & BP.NP. GI is in NP ∩ BP.coNP, its NP-hardness leads to PH = ∑2 .
[08-Apr-2014] [pdf] Probability amplification. Sipser-Gács' BPP is in ∑2.
[03-Apr-2014] [pdf] PTM Examples. RP, coRP, ZPP. ZPP = RP ∩ coRP.
[01-Apr-2014] [pdf] Amplify the parity of ⊕SAT. Toda's proof. Probabilistic TM.
[13-Mar-2014] [pdf] PH randomly reduces to ⊕P.
[11-Mar-2014] [pdf] PH vs. #P, ⊕P, Valiant-Vazirani's hashing technique.
[07-Mar-2014] [pdf] Valiant's theorem: per, on 0/1matrices, is #P-complete.
[04-Mar-2014] [pdf] #P-completeness, Permanent, per is in #P, cycle-cover of a graph.
[27-Feb-2014] [pdf] ∑2 = NPNP, Counting problems: #SAT, #P, PP.
[25-Feb-2014] [pdf] PH-conjecture, complete problems in PH, ∑iSat, ∏iSat.
[11-Feb-2014] [pdf] Nspace is closed under complement, the Polynomial Hierarchy PH.
[06-Feb-2014] [pdf] Savitch's theorem, NL-completeness.
[04-Feb-2014] [pdf] Pspace completeness, the QBF game.
[30-Jan-2014] [pdf] PB ≠ NPB, more space complexity.
[28-Jan-2014] [pdf] Ladner's theorem, oracles, relativizing proofs.
[25-Jan-2014] [pdf] Hierarchy theorems -- time, space, nondeterminism.
[23-Jan-2014] [pdf] Quadratic equations, coNP, NEXP, EEXP.
[21-Jan-2014] [pdf] Cook-Levin theorem, Karp reducibility, Integer programming.
[16-Jan-2014] [pdf] Nondeterministic TM, Ntime, Satisfiability (SAT).
[09-Jan-2014] [pdf] Complexity classes Dtime, P, NP & EXP.
[07-Jan-2014] [pdf] Church-Turing thesis, efficiency and the Halting problem.
[02-Jan-2014] [pdf] Formalizing problems & machines.
[31-Dec-2013] [pdf] Introduction & outline to Complexity.