For a single file with all the lectures by the instructor click here. For more, check below.
Instructor: Emanuele Viola.
Logistics.
Mondays 9:30 – 11:00am in 164 West Village H
Tuesdays 1:35 pm - 3:15 pm Ryder Hall 273. Office hours after class and by appointment.
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. Lower bounds from derandomization.
(4) Quasi-random groups. Austin’s corner theorem in SL(2,q). Regularity lemmas: TTV, Skorski
(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. Demaine’s advanced data structures class
(6) Arithmetic circuits. Overview. The chasm at depth 3. (The Gupta-Kamath-Kayal-Saptharishi result.) Shpilka and Yehudayoff’s survey Survey. Kumar’s concurrent class on arithmetic circuits.
(7) Fine-grained complexity reductions (SETH, 3SUM). SETH implies orthogonal vectors is hard. Faster orthogonal vectors via the polynomial method.
Each student will scribe #lectures/#students, and present a lecture. Grade is based on scribe, presentation, and class participation.
Scribes: due 48 hours from the time of the lecture. Feel free to send me a draft and ask for suggestions before the cutoff. Scribe templates: see the .tex files below. I also have a template for Lyx if you use it. 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:
A relaxaxation of bounded independence which does not fool AC0
Amnon Ta-Shma. Explicit, almost optimal, epsilon-balanced codes.
Unbalanced expander graphs from Parvaresh–Vardy codes: survey
Prahladh Harsha, Srikanth Srinivasan: On Polynomial Approximations to AC0
Improved parameters for bounded independence fools AC0
SAT algorithms for depth-2 threshold circuits:
Approximate degree:
Making polynomials robust to noise.
More Bun-Thaler we did not see (ask me about it).
Communication complexity:
Separating Deterministic from Randomized Multiparty Communication Complexity, Query-to-communication lifting for BPP (see their Table 1 for other interesting papers as well).
Separation of information and communication for boolean functions
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.
Fine-grained reductions:
Dynamic problems, LCS, edit distance.
There are many other reductions in this area.
Catalytic computation:
Survey, Buhrman, Cleve, Koucký, Loff and Speelman
More:
Fast Learning Requires Good Memory, see also this
the breakthrough on the cap-set problem