# 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

# 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