Princeton
University
|
Computer
Science 522
|
|
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
report).
Professor: Sanjeev Arora - 307 CS Building - 258-3869 arora@cs.princeton.edu Office hrs: Wed 2-3pm, or by appointment. (Or try dropping by any afternoon.)
Date; Lecture topoc |
Required reading |
Optional Reading |
Feb 1: Introduction to
course topics. Turing machine Model, Universal
TMs, Definition of P. |
Chapter 1 of text. |
|
Feb 3: P vs NP; NP-completeness and its
importance |
Chapter 2 of text. |
|
Feb 8: Diagonalization. Time Hierarchy
Thm and Nondeterministic Time Hierarchy. |
Chapter 3. (Section 3.3, Ladner's Thm, is
optional) |
Fortnow and Santhanam's new, more efficient
proof of Nondeterministic
Time Hierarchy Theorem. |
Feb 10: More remarks about
diagonalization. Space complexity. |
Chapter 4 |
|
Feb 15: Alternation. Polynomial
Hierarchy (bounded # of rounds of alternation). PSPACE
(polynomial # of rounds of alternation). Connection to
2-person games. |
Chapter 5, plus relevant sections of
Chapter 4 on PSPACE-completeness. |
|
Feb 17: Circuit complexity.
(Running theme: Using PH to explore complexity phenomena.)
|
Chapter 6. |
|
Feb 22: Randomized Computation, RP,
coRP, BPP. BPP is in PH. |
Chapter 7. |
|
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
Theorem |
Chapter 8 (but 8.3.3 is optional) |
|
Mar 2: Weak form of PCP Thm: NP is
in PCP(poly(n), 1). |
Chapter 11. |
A
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. |
Chapter 14.2 |
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. |
Chapter 14.3 |
|
Mar 21: Cryptography: Meaning of
encryption and its security. One way functions and
pseudorandom generators. Equivalence to next-bit
unpredictability. |
Chapter 9 |
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. |
Chapter 9. |
|
Mar 28: Hardness amplification.
Yao's XOR lemma. |
Chapter 19.1 |
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
Shaltiel. |
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
Theorem. |
22.1, 22.2 |
|
Apr 11: Finish Dinur's proof
(including the alphabet reduction.) Fourier
transforms. Use to prove correctness of linearity
test. |
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 |
Khot's
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
optional) |
|
April 25: Guest lecture by Avi Wigderson on
Natural Proofs (why we are stuck at proving circuit
lower bounds). |
Chapter 23 |
|
April 27: Another guest lecture by Avi
Wigderson. |
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.