Teaching special topics in complexity theory in Fall 2017

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


Emanuele Viola


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.

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.

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


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:

Here and here,

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.



Regularity lemmas:

TTV, Skorski

Fine-grained reductions:

Dynamic problems, LCS, edit distance.

There are many other reductions in this area.


  1. 2017-09-08 Fri
  2. 2017-09-12 Tue
  3. 2017-09-15 Fri
  4. 2017-09-19 Tue
  5. 2017-09-22 Fri
  6. 2017-09-26 Tue
  7. 2017-09-29 Fri
  8. 2017-10-03 Tue. Additive combinatorics workshop. NO CLASS
  9. 2017-10-06 Fri. Additive combinatorics workshop. NO CLASS
  10. 2017-10-10 Tue
  11. W-R Lectures by Gowers
  12. 2017-10-13 Fri
  13. 2017-10-17 Tue
  14. 2017-10-20 Fri
  15. 2017-10-24 Tue
  16. 2017-10-27 Fri
  17. 2017-10-31 Tue
  18. 2017-11-03 Fri
  19. 2017-11-07 Tue
  20. 2017-11-10 Fri
  21. 2017-11-14 Tue. Workshop. Class planned as usual, but check later
  22. 2017-11-17 Fri. Workshop. Class planned as usual, but check later
  23. 2017-11-21 Tue
  24. 2017-11-24 Fri. Thanksgiving, no classes.
  25. 2017-11-28 Tue
  26. 2017-12-01 Fri
  27. 2017-12-05 Tue
  28. 2017-12-08 Fri
  29. 2017-12-12 Tue
  30. 2017-12-15 Fri