Workshop Details

The PDF documents linked on this page, are no longer maintained and may not meet accessibility standards. To request an accessible version of any content, please contact us.

A traditional goal of complexity theory is to distinguish between problems that are computationally tractable and those that are not. The tractable, so-called “easy”, problems are solvable in polynomial time and form the complexity class P. From a practical standpoint, however, even problems solvable in cubic or quadratic time may be impossible when the input data is large enough. As problem sizes have grown, the need for a more nuanced understanding of the complexity of problems in
P gave rise to the relatively new field of fine-grained complexity.

Fine-grained complexity seeks to better-understand the complexity of problems in P. The central idea is to investigate relationships between different problems using fine-grained reductions, that not only preserve the worst-case running time but also the dependence on various parameters, such as input size, dimensionality, and sparsity. Such reductions enable more precise comparison of the relative difficulty of different problems, even when they have similar worst-case running times.

This tutorial will cover key concepts in fine-grained complexity. It will be taught at a beginning graduate school level and be based on courses on fine-grained complexity currently offered at only a few top universities. It will cover:

• The main conjectured-to-be-hard problems, what we know about them algorithmically, and how to reduce them to other problems. These problems include: k-SAT, 3-SUM, All-Pairs Shortest Paths, and k-Clique.
• Various examples of fine-grained results for important problems on strings (e.g. Edit-Distance), graphs (e.g. Diameter), and geometric data (e.g. Closest Pair).
• Other topics such as hardness of approximation and barriers for reductions.
• Research directions and open questions that are currently driving research in the field.

The format of the tutorial will include a mix of whiteboard technical lectures, presentations with slides surveying certain topics, materials and references that students may explore on their own, and problem-solving sessions.

The desired learning outcomes are:

• Ability to prove whether or not a problem is solvable in near-linear time. 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 is not equal to NP), this tutorial provides the tools to prove whether a problem is solvable in near-linear time or not (assuming certain conjectures).
• Familiarity with the most basic computational problems that are not known to be solvable in near-linear time.
• Ability to understand state-of-the-art research in fine-grained complexity.

Featured Lecturers:

• Amir Abboud, Senior Scientist, Department of Computer Science and Applied Mathematics, Weizmann Institute of Science
• Nick Fischer, Postdoctoral Fellow, Department of Computer Science and Applied Mathematics, Weizmann Institute of Science

Lecture materials: The links in the Program will take you to the slides for individual presentations. Alternatively, you can visit the Materials webpage for the Tutorial, which contains links to both lectures and exercises.

Exercise sheets:  [Prep sheet]  [3SUM]  [APSP]  [SETH]  [FGC in action]  [Miscellaneous]

Full video playlist

Code of Conduct