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 a month before the end of the semester
Progress Report (less than 2 pages) - due a couple weeks before the end
In-class presentation - around the end of the semester
(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.
Ryan's notes for 8/27 (course introduction, time-space tradeoffs for SAT, relativization) are here.
Scribe notes by Siqi Liu are coming soon.
Ryan's notes for 9/10 (time-space tradeoffs for branching programs with long output) are here.
Scribe notes by Chinmay Nirkhe are coming soon.
Ryan's notes for 9/17 (the hardest functions, and how to find them) are scribed (by Ryan) here.
The rough plan of topics (subject to change!)
Time-Space Tradeoffs: SAT, simple functions with many outputs
Generic Circuit Complexity: $\Theta(2^n/n)$ size, $\Sigma_2 P$ and $MA$ lower bounds, $MAEXP$ and $\Sigma_3 EXP$