Repeats every week every Tuesday and every Thursday until Tue Dec 10 2024 except Tue Oct 15 2024, Thu Nov 28 2024.

Thu, 09/05/2024 - 11:00am to 12:30pmLocation:

34-304

Instructor:

Virginia Vassilevska Williams, Ryan Williams

(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!**