Fine-Grained Algorithms and Complexity - An Overview of Exact Running Times

Explore a 25-minute conference talk from MIT Professor Virginia Vassilevska Williams at INSAIT 2022 that delves into the fascinating world of fine-grained algorithms and computational complexity. Learn about the evolution of algorithmic research, from classical algorithms of the 1950s and 1960s to modern approaches in determining computational problem-solving speeds. Discover why traditional NP-hardness reductions fall short when examining exact running times, particularly for polynomial-time solvable problems. Gain insights into the emerging field of "fine-grained reductions" developed over the past decade, which focuses on precise running time analysis rather than simple polynomial versus non-polynomial classifications. The presentation offers both an overview of this cutting-edge area and highlights recent breakthrough developments in computational complexity theory.