PODS Keynote
Speaker: Virginia Vassilevska Williams (MIT)
Title: A fine-grained approach to algorithms and complexity
Abstract: Algorithmic research aims to determine the optimal worst case running time for computational problems of interest. Time hierarchy theorems from complexity theory state that there are problems that, on inputs of size n, can be solved in t(n) time but not in đť‘‚(t(n)^{1-eps}) time for eps > 0. The main challenge is to determine where in the time hierarchy implied by the time hierarchy theorems various specific natural and important problems lie. Decades of algorithms research have culminated in an impressive toolbox of sophisticated techniques that have been applied to obtain fast algorithms for many problems. Nevertheless, for many other central problems, the best known running times are essentially those of their classical, often brute-force algorithms from the 1950s and 1960s.
Unconditional lower bounds seem very difficult to obtain, and so practically all known time lower bounds are conditional. For years, the main tool for proving hardness of computational problems have been NP-hardness reductions, basing hardness on P unequal NP. However, when we care about particular running times (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 two decades or so, a new theory has been developed, based on “fine-grained reductions” that focus on fixed running times. Mimicking NP-hardness, the approach is to (1) select a key problem X that is conjectured to require essentially t(n) time for some t, and (2) reduce X in a "fine-grained" way to many important problems, showing that their current best running time cannot be improved upon substantially unless X can be solved faster than in t(n) time. This approach has led to the discovery of many meaningful relationships between problems, and even sometimes to equivalence classes.
In this talk I will give an overview of this area of study, and will highlight some new developments related to databases.
Bio: Virginia Vassilevska Williams is a Professor at MIT EECS and CSAIL. She obtained her Ph.D. from Carnegie Mellon University in 2008. After research and postdoctoral positions at the IAS in Princeton, UC Berkeley and Stanford, she spent 3.5 years as an assistant professor at Stanford University before joining MIT in early 2017. She is the recipient of an NSF CAREER award, a Google Faculty Research Award, an Alfred P. Sloan Research Fellowship, a 2023 Simons Investigator Award and a FOCS 2024 Test of Time Award. In 2018 she gave an invited lecture at the International Congress of Mathematicians.
