This course explores the general problem of proving computational lower bounds, concrete limitations on computing. We study this problem on a completely abstract mathematical level, so that the results we prove are long-lasting, independent of ephemeral trends in technology. For a computational problem we care about solving often, we want to solve it with the minimum necessary resources. What is a resource? Anything scarce that a computation could consume: we can measure computation steps, memory usage, computation "size" and "depth" (if we consider Boolean logic circuits), energy consumption, communication between processors, number of processors, number of random bits used, number of qubits used, quality of approximate solutions, number of inputs correct(!) ... the list goes on.
What is the impact of limited resources on computation? Answers can vary based on the model of computation, and we will study many such models. We will also study how we may "trade" one resource for another: if I want to use less memory to solve a problem, how much more time do I need to take? For the most part, many interesting formalizations of these questions are infamous open problems in mathematics. (P vs NP is only one such formalization!)
Our main goal for this course is to explore topics in the mathematical theory of lower bounds, as it is presently known, and highlight many open problems in the subject. We will be biased towards topics closest to the instructor's expertise, but also we hope to highlight other approaches to the lower bound problem as we go. Along the way, we will learn whatever necessary math is needed to get the job done -- complexity theory often uses interesting math in unexpected ways.
This course is intended to complement the Fall'18 Simons Institute program on Lower Bounds. Because lower bounds can be a pretty forbidding subject to get into, our hope is that this in-depth course will help students get more out of the program.
Workload for this course:
Class Participation: Come to class! We'll start around 4:10pm, take a short break around 5:15, and end around 6:30 (or when the instructor is exhausted, whichever comes first).
There will be three Lower Bound workshops during the semester: Sep. 10 -- Sep. 14, Oct. 15 -- Oct. 19, Dec. 3 -- Dec. 7. Pick at least one talk during each workshop that you'd really like to learn about, attend it (or watch the video), and write a short email to me (3-4 paragraphs) with a "review" of the talk: the main statements, what you liked/disliked, what was clear/unclear, any ideas you got from watching it. Your email will be due on the Monday after the workshop.
Scribe one or two lectures.
Class Project (individual or with a partner). The idea is to explore a topic we didn't cover, and to either prove a new theorem about it, or write a short survey on the topic which could be useful to future researchers. The project has three components:
Project Proposal (less than 1 page) - due October 29, a month before the end of the semester
Progress Report (less than 2 pages) - due November 12, a couple weeks before the end
In-class presentation - on November 26, the last day of class. The schedule for presentations will be forthcoming. Final project report (about 4-5 pages) is due December 1 (please email if you need an extension).
(Optional)Open Problem Sessions(?) TBD. The idea would be to introduce open problems that a group of us discuss together, and try to say something interesting. We have successfully done this at MIT with a course on fine-grained complexity; lower bounds may be trickier. Let us know if you have an open problem that might be solved this way!
Prerequisites: This is an advanced course, intended for upper level undergraduate students and beginning graduate students in CS and Math, but it is open to anyone. You should definitely have knowledge at the level of both CS 170 (Efficient Algorithms and Intractable Problems) and CS 172 (Computability and Complexity). An advance grad course in complexity theory (such as CS 278) would also be useful, but not entirely necessary: in fact, we plan to cover a few results from that course. Sufficient mathematical maturity would probably suffice in lieu of CS 278.
Textbook: There is no textbook for the course, but we will have scribed lecture notes, and will catalog additional reading material as we go.
Announcements:
Ryan's notes for 8/27 (course introduction, time-space tradeoffs for SAT, relativization) are here.
Scribe notes by Siqi Liu are here.
Ryan's notes for 9/10 (time-space tradeoffs for branching programs with long output) are here.
Scribe notes by Chinmay Nirkhe are here.
Ryan's notes for 9/17 (the hardest functions, and how to find them) are scribed (by Ryan) here.
Ryan's notes for 9/24 (functions with and without small circuits) are here.
Scribe notes by Seri Khoury are here.
Ryan's notes for 10/1 (explicit functions without $3n$-size circuits) are scribed (by Ryan) here.
Ryan's notes for 10/8 (Parity not in $AC0$ via Switching Lemma) are here.
Scribe notes by Jonathan Schafer are here.
Ryan's notes for 10/15 and 10/22 (Razborov-Smolensky lower bounds against $AC0[p]$, start Beigel-Tarui) are here.
Scribe notes by Manuel Sabin are coming soon.
Ryan's notes for 10/29 (Beigel-Tarui representation of $ACC0$, $AC0$-SAT Algorithm, Circuit Analysis vs Circuit Lower Bounds) are here.
Scribe notes by Haaris Khan are here.
Ryan's notes for 11/5 (CircuitSAT implies Lower Bounds, Gap-CircuitSAT implies Lower Bounds) are here.
Scribe notes by Sidhanth Mohanty are coming soon.
Lecture on Friday 11/9 (Natural Proofs) notes are here.
Scribe notes by Nick Titterton are coming soon.
No lecture on 11/12 (Veteran's Day)
Guest Lectures on Friday 11/19 were cancelled due to smoke. At the moment, we don't have an extra lecture scheduled. In lieu of the lecture, Amir Yehudayoff suggested to read his survey on algebraic complexity, namely Sections 1, 2.2, 2.4, 3.4, 3.6, 4.1, and 4.3. This will help prepare you for the last workshop!
Don't forget: Dec 3 -- Dec 7 is the last workshop of the Simons semester!
The rough plan of topics (subject to change!)
Time-Space Tradeoffs: SAT, simple functions with many outputs $\surd$
Generic Circuit Complexity: $\Theta(2^n/n)$ size, $\Sigma_2 P$ and $MA$ lower bounds, $MAEXP$ and $E^{\Sigma_2 P}$ $\surd$