Announcements:
 Here is the exam, due on March 1st 10pm: [exam link].
 For the benefit of future offerings of this course, please fill out this feedback form.
 The fourth (and last) Problem Set is out! Due on January 26th.
 From now on, all lectures will be virtual: zoom link.
Course details:
Lectures: Mondays 2:154:00pm, via Zoom.
TA: Tomer Grossman.
Prerequisites: a basic course in Algorithms, and a basic course in Complexity/Computability.
Other: HW every other week, takehome exam, video recordings will (probably) be availble.
Topics by week:
25.10.21  Week 1: Overview. [Recording] [Slides] [Survey by Virginia Vassilevska Williams]
1.11.21  Week 2: 3SUM: Equivalent Versions. [Recording] [Notes]
8.11.21  Cancelled.
15.11.21  Week 3: 3SUM Hard Problems. [Recording] [Part 1: Slides] [Part 2: Notes]
22.11.21  Week 4: Triangles, Matrix Mult, and APSP [Recording] [Notes] [Notes from MIT]
29.11.21  Week 5: APSPHard Problems [Recording] [Notes]
6.12.21  Week 6: The Strong Exponential Time Hypothesis [Recording] [Notes] [Detailed notes from MPI] [More on SAT algorithms from MIT]
13.12.21  Week 7: SETHHard Problems. [Recording] [Notes: part 1, part 2]
20.12.21  Week 8: Hardness for Longest Common Subsequence. [Recording pw: fgcweizmann1] [Part 1: Slides and Detailed notes from MPI] [Part 2: Overview]
27.12.21  Week 9: Barriers for Reductions. [Recording] [Notes] [The NSETH paper]
3.1.22  Week 10: Dynamic Graph Problems. [Recording] [Slides+Notes]
10.1.22  Bonus Guest Lecture by Karthik C.S.: Hardness of Approximation and Parameterized Comeplxity. [Recording] [Slides]
17.1.22  Week 12: kClique. [Recording] [Slides+Notes]
24.1.22  Week 13: Conclusion. [Feedback form] [Recording] [Slides+Notes]
Problem Sets:
 [HW4  due 26.1]
 [HW3  due 2.1]
 [HW2  due 15.12]
 [HW1  due 23.11] [Sample solution] [Helpful resource on randomness from the the FGC course at MPI]
List of open questions that we saw in class (ideas for research projects): [Open Questions]
Syllabus:
Whereas traditional complexity theory classifies problems into polynomial time solvable (easy) or NPhard, a more modern complexity theory aims to achieve a more finegrained classification. For example, we'd like to know if the time complexity is nearlinear or quadratic? This is motivated by the fact that, with the growing sizes of data, even quadratic time can be impractical.
This course will present the current approach for obtaining finegrained complexity results: we start with a small set of conjectures (similar to P \neq NP) about the exact complexity of certain core problems and devise a host of combinatorial reductions to achieve finegrained lower bounds for many other problems.
The course will cover:
 The main conjecturedtobehard problems, what we know about them algorithmically, and how to reduce them to other problems. These problems include: kSAT, 3SUM, AllPairs Shortest Paths, and kClique.
 Various examples of finegrained results for important problems on strings (e.g. EditDistance), graphs (e.g. Diameter), and geometric data (e.g. Closest Pair).
 Other topics such as hardness of approximation, parameterized complexity, and barriers for reductions.
Learning outcomes:
 Whereas a basic course in complexity theory provides the students with tools to prove whether a problem that they encounter is in P or not (assuming P \neq NP), this course provides them with tools to prove whether a problem is in nearlinear time or probably not (assuming certain conjectures).
 Familiarity with the most basic computational problems that are not known to be solvable in nearlinear time.
 Ability to understand state of the art research in finegrained complexity.
Helpful resources on "Hardness in P":

Surveys:
 SETH vs Approximation, SIGACT News 2019 by Rubinstein and Vassilevska Williams.

On some finegrained questions in algorithms and complexity, ICM 2018 survey by Vassilevska Williams.

Some Open Problems in FineGrained Complexity, SIGACT News 2018 by Vassilevska Williams.

Tutorial Slides for the Highlight of Logic, Games, and Automata 2018.
 Hardness in P, Ph.D. thesis (2017)

Recent Developments in Hardness in P, survey talk slides (Simons Reunion 2017).

The New P, 20min video from the 2016 Simons workshop, Slides of longer version.

Courses:

FineGrained Algorithms and Complexity course at MIT by Virginia Vassilevska Williams and Ryan Williams, Fall 2020.

Algorithms from the FineGrained Perspective, course at UIUC by Timothy Chan, Fall 2020.

FineGrained Complexity Theory course at MPI by Karl Bringmann and Marvin Kunnemann, Summer 2019.

 Workshops:

FineGrained Complexity (TAU theory fest 2020).

Fine Grained Approximation Algorithms and Complexity (Bertinoro 2019).

Structure and Hardness in P (Dagstuhl 2016).

Computational Complexity of LowPolynomial Time Problems (Simons Institute 2016).
 Hardness and Equivalences in P (STOC 2015).


Open problem lists: Dagstuhl 2016.