Special topics in complexity theory

For a single file with all the lectures by the instructor click here. For more, check below.

Instructor: Emanuele Viola.


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.


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


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.



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


Fast Learning Requires Good Memory, see also this

the breakthrough on the cap-set problem


  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.
    Lecture 19.pdf, Lecture 19.tex, Lecture 19 blog post.

Some presentations by students

  1. Matthew Dippel, pdf, tex
  2. Xuangui Huang, pdf, tex
  3. Chin Ho Lee, pdf, tex
  4. Tanay Mehta, pdf, tex
  5. Willy Quach, pdf, tex