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
- August 27:
Introduction, circuit complexity, $AC^0$ and related classes, the $SAT$-problem,
switching lemma
- Recommended: Aug 31- Sept 4, Fine-grained complexity boot camp
- September 1:
Proof of switching lemma, lower bound for constant depth circuits, use of switching lemma
for $k$-SAT algorithml
- September 3:
Razborov-Smolensky lower bound method
- September 8:
Using the RS method in improving polynomial-time algorithms
- September 10:
$ACC^0$ polynomial representations and $ACC^0$-SAT
- September 15-17
Hardness to randomness
- September 22-24
Hardness from derandomization and the easy witness lemma
- Recommended: Connections between algorithm design and complexity theory workshop, September 28- October 1
- September 29 , October 1
Lower bound for $ACC_0$
- October 6-8
Algorithms for NP-complete problems
- October 13-15
Sparsification, Exponential Time Hypothesis, and its consequences for the exact complexity of
NP-complete problems
- October 20-29
Parameterized algorithms, kernalization, and parametrized complexity
- Recommended: November 2- 6
Workshop: Satisfiability lower bounds, and Tight Results for Parameterized and
Exponential Time Algorithms
- November 3, 7 : Consequences of ETH for parameterized algorithms
- November 10, 12: Some consequences of ETH and SETH for algorithms within $P$
- November 17, 19: Other conjecutres with consequences for problems within $P$
- November 24: Fine-grained structure of $P$
- Recommended : Nov 30- Dec 4
Complexity of Low-Polynomial Time Problems workshop
- December 1 -10 : Student presentations
Lecture Notes
Antonina Kolokolova's notes with recording
- Lecture 1
- Lecture 2
- Lecture 3
- Lecture 4
- Lecture 5
- Lecture 6
- Lecture 7
- Lecture 8
- Lecture 9
- Lecture 10
- Lecture 11
- Lecture 12
- Lecture 13