CS 294-152. Lower Bounds: Beyond the Bootcamp -- Fall 2018

Instructors: Ryan Williams
Time: Mondays 4:10pm to $\approx$ 6:30pm, Soda 405
Office Hours: TBA
URL: http://bit.ly/LB-COURSE


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:

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: The rough plan of topics (subject to change!)
  1. Time-Space Tradeoffs: SAT, simple functions with many outputs $\surd$
  2. Generic Circuit Complexity: $\Theta(2^n/n)$ size, $\Sigma_2 P$ and $MA$ lower bounds, $MAEXP$ and $E^{\Sigma_2 P}$ $\surd$
  3. Lower Bounds by Gate Elimination $\surd$
  4. $AC0$ Lower Bounds: Hastad's Switching Lemma $\surd$
  5. $AC0$ modulo a prime: Razborov-Smolensky $\surd$
  6. $ACC0$ Lower Bounds: Beigel-Tarui $\surd$, ACC-SAT Algorithm $\surd$, Easy Witness Lemmas $\surd$, SAT Algorithms imply Circuit Lower Bounds $\surd$
  7. Natural Proofs: As a Barrier, As an Oracle (MCSP), Constructive and Useful = NEXP Lower Bounds $\surd$
  8. Guest Lectures on Arithmetic Circuit Complexity, Data Structure Lower Bounds, ...