Instructor.
Logistics.
Class 1:35 pm - 3:15 pm Tuesday Friday Ryder Hall 273.
First class Sep 08, 2017.
Running at the same time Program on Combinatorics and Complexity at Harvard.
This class will present recent (amazing) progress in complexity theory and related areas. A highly tentative list of topics follows:
(1) Pseudorandom generators. Bounded independence, small-bias, sandwiching polynomials. Bounded independence fools And, bounded independence fools AC0 (Braverman’s result), the Gopalan-Kane-Meka inequality, the Gopalan-Meka-Reingold-Trevisan-Vadhan generator. Vadhan’s survey, Amnon Ta-Shma’s class
(2) Approximate degree. Bounded indistinguishability. Bounded indistinguishability of Or, And-Or, and Surjectivity (the Bun-Thaler proof)
(3) Circuit complexity. Williams’ lower bounds from satisfiability. Succinct and explicit NP-completeness. ACC0-SAT algorithms. Exposition in web appendix of Arora and Barak’s book.
(4) Quasi-random groups. Austin’s corner theorem in SL(2,q).
(5) Communication complexity and quasi-random groups. Determinism vs. randomization in number-on-forehead communication complexity. Number-in-hand lower bounds for quasi-random groups. Various notes.
(5) Data structures. Overview: static, dynamic, bit-probe, cell-probe. Siegel’s lower bound for hashing. The Larsen-Weinstein-Yu superlogarithmic lower bound.
(6) Arithmetic circuits. Overview. The chasm at depth 3. (The Gupta-Kamath-Kayal-Saptharishi result.) Shpilka and Yehudayoff’s survey Survey
(7) Fine-grained complexity reductions (SETH, 3SUM)
Each student will scribe #lectures/#students, and present a lecture. Grade is based on scribe, presentation, and class participation.
Scribes: due 72 hours from the time of the lecture. Feel free to send me a draft and ask for suggestions before the cutoff. Scribe templates: lyx, tex. Optionally, the lectures will be posted on my blog. Using this template minimizes the risk that my wordpress compiler won’t work.
Presentations: should convey both a high-level overview of the proof of the result, as well as a self-contained exposition of at least one step. Talk to me for suggestions. Discuss with me your presentation plan at least 1 week before your presentation.
Presentation papers:
Note: Always look if there is an updated version. Check the authors’ webpages as well as standard repositories (arxiv, ECCC, iacr, etc.)
Pseudorandomness:
Amnon Ta-Shma. Explicit, almost optimal, epsilon-balanced codes.
Prahladh Harsha, Srikanth Srinivasan: On Polynomial Approximations to AC0
SAT algorithms for depth-2 threshold circuits:
Quasirandom groups:
Data structures:
Parts of Larsen-Weinstein-Yu superlogarithmic we left out.
Any of the many lower bounds we didn’t see.
Arithmetic circuit complexity:
Parts of the reduction we did not see.
Regularity lemmas:
Fine-grained reductions:
Dynamic problems, LCS, edit distance.
There are many other reductions in this area.