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

Instructor.

Emanuele Viola

Logistics.

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)

Deliverables

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

Pseudorandomness:

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.

Survey

Tavenas

Regularity lemmas:

TTV, Skorski

Fine-grained reductions:

Dynamic problems, LCS, edit distance.

There are many other reductions in this area.

Classes

  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
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s