Grading: 60% of the grade will be based upon
assignments, which will be handed out every two weeks. 40% will
be based upon a long take-home final (open book).
Every student taking the course will have the responsibility to grade the homework once during the term, under my supervision.
Students who wish to explore an advanced topic can substitute
one homework with a small reading project (with a 3-page
|Date; Lecture topoc
|Feb 1: Introduction to
course topics. Turing machine Model, Universal
Definition of P.
|Chapter 1 of text.
|Feb 3: P vs NP; NP-completeness and its
||Chapter 2 of text.
|Feb 8: Diagonalization. Time Hierarchy
Thm and Nondeterministic Time Hierarchy.
||Chapter 3. (Section 3.3, Ladner's Thm, is
||Fortnow and Santhanam's new, more efficient
proof of Nondeterministic
Time Hierarchy Theorem.
|Feb 10: More remarks about
diagonalization. Space complexity.
|Feb 15: Alternation. Polynomial
Hierarchy (bounded # of rounds of alternation). PSPACE
(polynomial # of rounds of alternation). Connection to
||Chapter 5, plus relevant sections of
Chapter 4 on PSPACE-completeness.
|Feb 17: Circuit complexity.
(Running theme: Using PH to explore complexity phenomena.)
|Feb 22: Randomized Computation, RP,
coRP, BPP. BPP is in PH.
|Feb 24: Finish randomized computation;
start Interactive proofs. Definition, robustness
of model, private vs public coins etc.
||Chapter 8 up to section 8.2.
||Babai's survey on Email
and the unexpected power of interaction.
|Feb 29: Interactive proofs for #SAT; sketch
of IP =PSPACE. Begin discussion of PCP
||Chapter 8 (but 8.3.3 is optional)
|Mar 2: Weak form of PCP Thm: NP is
in PCP(poly(n), 1).
history of the PCP Theorem by Ryan O'Donnell.
(Informal notes.) For the record, I don't recall any nude
bungee jumping at that 1992 conference.
|Mar 7: Circuit lower bounds: Lower bounds
for ACC(q) circuits.
||We didn't talk about a large research
effort on proving lower bounds for algebraic circuits more
generally; see the 2010
survey by Shpilka and Yehudayoff.
|Mar 9: More circuit lower bounds: Razborov
lower bound for monotone circuits.
|Mar 21: Cryptography: Meaning of
encryption and its security. One way functions and
pseudorandom generators. Equivalence to next-bit
||Cryptography textbooks by Goldreich, or
Katz and Lindell, or Boneh and Shoup.
|Mar 23: Cryptography (contd): Goldreich-Levin
theorem; pseudorandom functions; partial derandomization
of BPP using PRG's.
|Mar 28: Hardness amplification.
Yao's XOR lemma.
||Yao's lemma at first seems like it should
be greatly improveable but it is known that some of the
intuitive conjectures are wrong. See this paper by
|Mar 30: Hardness vs Randomness. Nisan-Wigderson generator. Derandomization under complexity theoretic assumptions.||Chapter 20.1, 20.2
||A 2007 survey by Impagliazzo
on Hardness vs Randomness.
|Apr 4: Expanders and their pseudorandom properties. Reingold's theorem (logspace algorithm for undirected connectivity).||Chapter 21.1, 21.4
||21.2 was touched upon but not explained in
class. Some of the definitions (eg replacement product)
are in 21.3
Expander graphs and their applications by
Hoory, Linial, Wigderson. (JAMS 2006).
|Apr 6: Dinur's proof of PCP
|Apr 11: Finish Dinur's proof
(including the alphabet reduction.) Fourier
transforms. Use to prove correctness of linearity
||22.3, 22.4, 22.5
|Apr 13: Quantum computing: the
model. Simon's algorithm for detecting the period.
||10.1, 10.2, 10.3, 10.5
||10.2.1 (EPR paradox) is optional but
recommended. 10.6 (Shor's algorithm) was only sketched.
|Apr 18: More advanced use of fourier
transforms in PCPs. Long code test. Unique games
conjecture and PCPs.
||22.6, with a peek at 22.9.4
survey on Unique Games Conjecture and its implications.
|April 20: Counting Complexity, and
Toda's Theorem. Implications for circuit complexity.
||Chapter 17 (but 17.3.1 and 17.3.2 are
|April 25: Guest lecture by Avi Wigderson on
Natural Proofs (why we are stuck at proving circuit
|April 27: Another guest lecture by Avi
Honor Code for this class
Collaborating with your classmates on assignments is encouraged (and may be essential to get the most out of the course). You must, however, list your collaborators for each problem. The assignment questions have been carefully selected for their pedagogical value and may be similar to questions on problem sets from past offerings of this course or courses at other universities. Using any preexisting solutions from these or any other sources is strictly prohibited.