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

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.

- 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 1 : Switching Lemma, part 1
- Lecture 2 : Switching Lemma, part 1
- Lecture 3 : Using Switching Lemma for Learning ala LMN
- Lecture 4: LMN continued
- Lecture 5: Razborov-Smolensky probabilistic polynomial method
- Ryan Williams Guest Lecture on using probabilistic polynomials for algorithms
- Lecture 8
- Lecture 9
- Reference one for Thore Husfeldt's guest lectures
- Reference two for Thore Husfeldt's guest lectures
- Lecture 10
- Lecture 11
- Lecture 12
- Lecture 13
- Daniel Marx's guest lecture
- Lecture 16
- Lecture 20 (just a guess)