Next Fall I am teaching a special topics class in complexity theory. Below and here is the formal announcement, including a highly tentative list of topics. Some of the topics are somewhat ambitious, but that problem lies well in the future, concerning not me but my future self. He also appreciates suggestions and pointers of cool results to include.
Special topics in complexity theory
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.
Note: Always look if there is an updated version. Check the authors’ webpages as well as standard repositories (arxiv, ECCC, iacr, etc.)
Amnon Ta-Shma. Explicit, almost optimal, epsilon-balanced codes.
(Perhaps Avraham Ben-Aroya, Dean Doron and Amnon Ta-Shma. An efficient reduction from non-malleable extractors to two-source extractors, and explicit two-source extractors with near-logarithmic min-entropy.)
Prahladh Harsha, Srikanth Srinivasan: On Polynomial Approximations to AC0
SAT algorithms for depth-2 threshold circuits:
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.
Dynamic problems, LCS, edit distance.
There are many other reductions in this area.
- 2017-09-08 Fri
- 2017-09-12 Tue
- 2017-09-15 Fri
- 2017-09-19 Tue
- 2017-09-22 Fri
- 2017-09-26 Tue
- 2017-09-29 Fri
- 2017-10-03 Tue. Additive combinatorics workshop. NO CLASS
- 2017-10-06 Fri. Additive combinatorics workshop. NO CLASS
- 2017-10-10 Tue
- W-R Lectures by Gowers
- 2017-10-13 Fri
- 2017-10-17 Tue
- 2017-10-20 Fri
- 2017-10-24 Tue
- 2017-10-27 Fri
- 2017-10-31 Tue
- 2017-11-03 Fri
- 2017-11-07 Tue
- 2017-11-10 Fri
- 2017-11-14 Tue. Workshop. Class planned as usual, but check later
- 2017-11-17 Fri. Workshop. Class planned as usual, but check later
- 2017-11-21 Tue
- 2017-11-24 Fri. Thanksgiving, no classes.
- 2017-11-28 Tue
- 2017-12-01 Fri
- 2017-12-05 Tue
- 2017-12-08 Fri
- 2017-12-12 Tue
- 2017-12-15 Fri