Speaker: Virginia Vassilevska Williams (Stanford University)

Abstract

A central goal of algorithmic research is to determine how fast computational problems can be solved in the worst case. 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-\varepsilon}$ time for $\varepsilon>0$. The main challenge is to determine where in this hierarchy various natural and important problems lie. Throughout the years, many ingenious algorithmic techniques have been developed and applied to obtain blazingly fast algorithms for many problems. Nevertheless, for many other central problems, the best known running times are essentially those of the classical algorithms devised for them in 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$\neq$NP. However, when we care about the exact running time (as opposed to merely polynomial vs non-polynomial), NP-hardness is not applicable, especially if the running time is already polynomial. In recent years, a new theory has been developed, based on \emph{``fine-grained reductions''} that focus on exact running times. The goal of these reductions is as follows. Suppose problem $A$ is solvable in $a(n)$ time and problem $B$ in $b(n)$ time, and no $a(n)^{1-\varepsilon}$ and $b(n)^{1-\varepsilon}$ algorithms are known for $A$ and $B$ respectively. The reductions are such that whenever $A$ is fine-grained reducible to $B$ (for $a(n)$ and $b(n)$), then a $b(n)^{1-\varepsilon}$ time algorithm for $B$ (for any $\varepsilon>0$) implies an $a(n)^{1-\varepsilon'}$ algorithm for $A$ (for some $\varepsilon'>0$). Now, mimicking NP-hardness, the approach is to (1) select a key problem $X$ that is conjectured to require $t(n)^{1-o(1)}$ time, and (2) reduce $X$ in a fine-grained way to many important problems. 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 the current progress in this area of study, and will highlight some new exciting developments.