Title: Fine-Grained Complexity


Abstract:

This talk will motivate and overview the large body of works aiming to understand the precise polynomial in the running time of fundamental problems by relying on the conjectured hardness of a small set of core problems. The featured results include tight bounds for classical problems on graphs, strings, geometric data, and more. We will also discuss the impact on algorithm design and survey several directions that are at the frontier of research in this field.

Livestream/Recording: https://huji.cloud.panopto.eu/Panopto/Pages/Viewer.aspx?id=05906898-f738-4a1c-b611-b171005a64de