6.1420/S974 Fine-Grained Complexity and Algorithms

(Optional) Weekly OPEN Problems Sessions alongside the course-- these often lead to publications!

NP-hardness has been very successful in explaining why many problems seem to lack polynomial-time algorithms. However, “polynomial time” is often still too inefficient. For domains with large inputs, super-linear-time algorithms are already unacceptably slow.

For many problems we want to know:

(1) What is the best running time exponent?

(2) Why don’t we have a faster algorithm?

(3) Are we stuck on these problems for the same reason?

Fine-grained complexity is a developing subject which offers explanations of why many algorithmic problems have resisted significant algorithmic improvement for decades.

Come to 6.1420 to learn these new ideas, and to work on cool open problems yourself!

Fine-grained complexity has given novel explanations of hardness in many research areas such as: Graph Algorithms, Machine Learning, Dynamic Algorithms, Computational Geometry, Distributed Algorithms, Cryptography, External Memory Algorithms, etc.

6.1420 will give you tools to find new lower bounds in your sub-field of interest!