Fine-Grained Complexity and Algorithms

CS 294-114

Instructor: Russell Impagliazzo

Department of Computer Science and Engineering
University of California, San Diego
La Jolla, CA 92093-0114
On sabattical at Room 344, Calvin Labs, Simons Institure
UC, Berkeley campus

Email: russell@cs.ucsd.edu

Tuesdays and Thursdays , 5:00-6:30, SODA 405

Course description:

Traditionally, complexity theory has been used to distinguish very hard problems (such as NP-complete problems) from relatively easy problems, such as those solvable in polynomial time. Recent directions in complexity and algorithms have enabled us to use similar methods to reason about the complexity of problems at a {\em finer grained level}, distinguishing between say problems requiring quardratic time from those solvable in linear time, between those NP-complete problems requiring exhaustive search from those where there are significant improvements over exhaustive search, and between those parameterized problems with say dependency exponential in a parameter but a fixed polynomial in the input size, and those where the exponent of the input size grows with the paramemter.

This new theory of fine-grained complexity shows relationships amongst the exact complexity of all three categories of problem above. Moreover, and perhaps more surprisingly, the notion of exact complexity provides a way to link progress in algorithm design to progress in proving lower bounds, especially for non-uniform models.

This course will survey these developments. It will be self-contained, but run in tandem with the Simons Institute semester on Fine-Grained Complexity and Algorithms. One goal of the class will be to provide graduate students with sufficient background to participate fully in the Simons Institute semester. There will be occasional guest speakers from the Simons Institute program, presenting recent (or even just obtained) research results related to course materials.

Prerequisites:

We will assume that students have had at least some exposure to algorithms and their analysis (with familiarity with randomized algorithms and dynamic programming), and basic complexity theory (e.g., familiarity with the concept of NP-completeness). Otherwise, the class will be self-contained, developping new concepts as needed.

Assignments:

Students taking the class for credit will be expected to contribute scribe notes for two lectures each (unless there are more than 13 students signed up, in which case it may be reduced to one), and to read and present in a group of up to four a recent research paper related to a course topic.

Tentative schedule of topics

  • Lecture Notes

    Antonina Kolokolova's notes with recording

    1. Lecture 1
    2. Lecture 2
    3. Lecture 3
    4. Lecture 4
    5. Lecture 5
    6. Lecture 6
    7. Lecture 7
    8. Lecture 8
    9. Lecture 9
    10. Lecture 10
    11. Lecture 11
    12. Lecture 12
    13. Lecture 13