Prof. Virginia Vassilevska Williams (MIT), INSAIT 2022 Conference: Fine-Grained Algorithms...

Fine-Grained Algorithms and Complexity A central goal of algorithmic research is to determine how fast computational problems can be solved in the worst case. Unfortunately, for many central problems, the best-known running times are essentially those of their classical algorithms from the 1950s and 1960s. For years, the main tool for explaining computational difficulty has been NP-hardness reductions, basing hardness on P≠NP. However, if one cares about exact running time (as opposed to merely polynomial vs non-polynomial), NP-hardness is not applicable, especially if the problem is already solvable in polynomial time. Over the last decade, a new theory has been developed, based on “fine-grained reductions” that focus on exact running times. In this talk I will give an overview of this area, and will highlight some exciting new developments.