Special topics in complexity theory

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.

Tentative syllabus

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.

Deliverables

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.

(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.)

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:

Here and here.

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:

Higher-dimensional corners

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.

Survey

Tavenas

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

Classes

  1. 2017-09-12 Tue. Basics of PRGs. Bounded independence. Lecture 1.pdf, Lecture 1.tex, Lecture 1 blog post
  2. 2017-09-18/19. Bounded independence fools And, fools AC0. Lectures 2-3.pdf, Lectures 2-3.tex, Lectures 2-3 blog post
  3. 2017-09-25/26. Small-bias. Almost bounded independence. Fourier analysis. Vazirani xor lemma. The GMRTV generator Lectures 4-5.pdf, Lectures 4-5.tex, Lectures 4-5 blog post
  4. 2017-10-02/03 Additive combinatorics workshop. NO CLASS
  5. 2017-10-09/10 Monday holiday: no class. Bounded indistinguishability. Approximate degree. Duality.
  6. W-R Lectures by Gowers
  7. 2017-10-16/17 Monday: Approximate degree of Or. Approximate degree of And-Or. Tuesday: 10-minute pre-presentations by students. Lectures 6-7.pdf, Lectures 6-7.tex, Lectures 6-7 blog post
  8. 2017-10-23/24 Finish approximate degree of And-Or. Approximate degree of SURJ. Quasirandom groups. Lectures 8-9.pdf, Lectures 8-9.tex, Lectures 8-9 blog post
  9. 2017-10-30/31 Guest lecture by Justin Thaler. Presentation by Giorgos. Lecture 10.pdf, Lecture 10.tex, Lecture 10 blog post
  10. 2017-11-06/07 Quasirandom groups. Number-in-hand communication complexity of quasirandom groups. 2-party interleaved communcation. Lectures 12-13.pdf, Lectures 12-13.tex, Lectures 12-13 blog post.
  11. 2017-11-13/14 Workshop. NO CLASS. To make up we’ll meet Monday 9:30 - 12:30 and Tue 1:35 - 3:45 until the end.
  12. 2017-11-20/21 Monday: Presentation by Chin and Xuangui. Tuesday: Number-on-forehead communication complexity. Determinism vs. randomization. Reduction to corners theorem. Lecture 15.pdf, Lecture 15.tex, Lecture 15 blog post.
  13. 2017-11-27/28 Monday: Presentation by Biswaroop. Monday.2: Weak regularity lemma. Tuesday: Corners theorem. Lectures 16-17.pdf, Lectures 16-17.tex, Lectures 16-17 blog post.
  14. 2017-12-04/05 Monday: Presentation by Willy. Tuesday: Static data structure lower bounds. Lecture 18.pdf, Lecture 18.tex, Lecture 18 blog post.
  15. 2017-12-11/12 Monday: Presentations by Matthew and Tanay. Tuesday: Guest lecture by Huacheng Yu.