Date  Topic 
Dec 31 
Natural proofs and algebrization: the wild world of barriers in proving lower bounds. 
Dec 29 
Introduction to twoparty Communication Complexity. Applications to streaming lower bounds and timespace tradeoffs. 
Dec 24 
An introduction to algebraic complexity theory by Youming 
Dec 22 
The fundamental theorem of privatekey crypto: equivalence of PRGs  OWFs  PRFGs. The GoldreichLevin hardcore bit theorem.
Elements of PCPs and holographic proofs.

Dec 17 
Introduction to foundations of Cryptography, intractability assumptions, private vs publickey crypto,
can we get publickey crypto from OWFs? 
Dec 15 
Interactive computation, AM=AM[2], is Graph Isomorphism NPcomplete? , arithmetization, IP=PSPACE, program checkers 
Dec 10 
Exponential monotone circuit lower bounds for CLIQUE.

Dec 8 
Finishup the proof of the switching lemma.

Dec 3 
Hastad's switching lemma. PARITY not in AC^0.

Dec 1 
Back to nonrandomized computation: revisiting PH and the KarpLipton theorem,
Alternating Turing Machines, the nature of PH  relations to circuit families, more results in concrete Circuit Complexity.

Nov 26 
From hard functions to pseudorandom generators, the NisanWigderson pseudorandom generator,
KabanetsImpagliazzo (details on KI by Youming in next week's recitation) 
Nov 24 
Introduction to pseudorandom generators, PRGs in cryptography vs PRGs in complexity theory.
Yao's unpredictability implies pseudorandomness. 
Nov 21 (4 hrs) 
Hardness amplification, Yao's XOR lemma, Impagliazzo's hardcore lemma,
applying ECC to obtain average from worstcase hardness. 
Nov 19 
BPP contained in P/poly and Sigma(2) intersect Pi(2) 
Nov 17 
Hitting property of expander RWs, introduction to the polynomial hierarchy. 
Nov 12 
UREACH in LOGSPACE (the details on the zigzag product in the recitation), reducing randomness in efficient computation through RWs,
other applications of expander graphs. 
Nov 10 
Notions of pseudorandomness, statements about random objects, sides of error RP, coRP, BPP, main properties and common fallacies. 
Nov 5 
Random walks on finite graphs and expander graphs, the spectrum of an undirected graph, notions of expansion and their relations 
Nov 3 
Elements of the probabilistic method, pseudorandom objects, introduction to expander graphs,
existence of bipartite expanders, expander mixing lemma,
randomness in efficient computation vs randomness in cryptography,
distributed computing... 
Oct 29 
Savitch's theorem, QBF is complete for PSPACE, RL and complete problems 
Oct 22 
Verifying NPwitnesses with limited resources, one vs twoway nondeterministic tape, inductive counting, NL=coNL 
Oct 20 
Complete problems for P, space bounded computation, Turing Machine space and circuit depth, NLcompleteness 
Oct 15

Uniform vs nonuniform circuits, the NC and AC hierarchies, the role of reductions, new types of reductions, more relations and more conjectures 
Oct 13

Proof of CookLevin, NPcompleteness and selfreducibility, formulas vs circuits, introduction to spacebounded computation 
Oct 9 
Ladner's theorem, candidates between P and NPcomplete, more on nondeterminism, proofs and certificates, computation is local, CookLevin (proof sketch) 
Oct 8 
Baker/Gill/Solovay theorem, Ladner's theorem (proof sketch) 
Sept. 29 
Oracle Turing machines, relativization, Baker/Gill/Solovay theorem (begin), nondeterminism 
Sept. 26 (4 hrs) 
Constructibility, padding, space/time hierarchy and consequences. Oracles and relativization 
Sept. 17 
Introduction: models of computation, resources, Turing Machines, speedup/tape compression 