General Information
 Instructor: Josh Alman
 Time: Tuesdays 4:10 – 6:00 PM
 Classroom: 451 Computer Science Building (directions)
 TA: Yuval Efron
 Office Hours:
 Josh: Thursdays 4 – 5 PM in CSB 504 or by email/appointment
 Yuval: Tuesdays 3 – 4 PM in location TBA or by email/appointment
 Scribe Notes will be posted below
Description
The theory of NPhardness is able to distinguish between "easy" problems that have polynomialtime algorithms, and "hard" problems that are NPhard. However, it is often not reasonable to label any problem with a polynomialtime algorithm as "easy", and in practice, it can make a huge difference whether an algorithm runs in, say, linear time, quadratic time, or cubic time. Nonetheless, the theory of NPhardness is "too coarse" to make distinctions like this.
FineGrained Complexity is a new area which aims to address this issue. The theory involves careful "finegrained reductions" between problems which show that a polynomial speedup for one problem would give a polynomial speedup for another. Through a web of such reductions, FineGrained Complexity identifies a small number of algorithmic problems whose bestknown algorithms are conjectured to be optimal, and shows that assuming these conjectures, a wide variety of algorithms in many seeminglydifferent areas must also be optimal.
In this class, we will explore this new area and a variety of applications. We will study problems like Orthogonal Vectors, 3SUM, and AllPairs Shortest Paths, which are at the center of these conjectures, and see why we believe they are (or aren't?) difficult. We will give finegrained reductions from these problems to problems in many areas, including dynamic and approximation algorithms problems. We will also study the related area of parameterized complexity, which shows how NPhard problems can become tractable when certain parameters describing the input are guaranteed to be small.
Evaluation will be primarily based on a final project. I will provide a list of suggestions for the project, but students are encouraged to relate their project to their interests. There will also be occasional (at most 3) homework assignments, and students will be asked to scribe a lecture.
Prerequisites
This is an advanced topics class in theoretical computer science, but it is open to everyone. The most important prerequisite is mathematical maturity (comfort with understanding and writing mathematical proofs). Students should also be very comfortable with algorithmic concepts and NPcompleteness (e.g., from CSOR 4231).
Tentative Schedule
September 6 
Introduction to the course. SETH, OV, and finegrained reductions. 

September 13 
SAT Algorithms: Sparsification, PPSZ, and improvements. 

September 20 
OVHardness of Sequence Problems: Longest Common Subsequence, Edit Distance, Fréchet Distance. 

September 27 
APSP: Connections to (min,+)product, negative triangles, other applications. 

October 4 
The polynomial method: Fastest known algorithms for OV and APSP. 

October 11 
kSUM: algorithms, variants, applications to computational geometry. 

October 18 
Hardness of dynamic problems: SETHbased lower bounds, online matrixvector multiplication. 

October 25 
Algorithms in other models: linear decision trees, nondeterministic algorithms, barriers for finegrained reductions. 

November 1 
Parameterized Complexity day 1: introduction, Vertex Coloring, kernelization. 

November 8 
No meeting (Election Day) 

November 15 
Parameterized Complexity day 2: W hierarchy, connections with (S)ETH. 

November 22 
Epilogue 

November 29 
Student Presentations day 1. 

December 6 
Student Presentations day 2. 

Other Resources
There is no textbook for this course, but we will write lecture notes over the course of the semester. The following survey and similar courses could also be helpful resources.
 Survey by Virginia Vassilevska Williams (link)
 Course by Virginia Vassilevska Williams and Ryan Williams (link)
 Course by Karl Bringmann (link)
 Course by Timothy Chan (link)
 Course by Amir Abboud (link)