Virginia Williams: 2014 Plenary Session

Tuesday, April 15, 2014
Location: Fisher Conference Center, Arrillaga Alumni Center

"Hardness for Easy Problems"
3:00pm

Abstract:

There are many important computational problems that have simple polynomial time algorithms. Yet, for practical applications, merely polynomial time is insufficient. We would like extremely fast solutions, hopefully linear time. However, often the simple polynomial time solution seems to be the best known.

In biology applications for instance, sequence alignment problems such as computing the longest common substring of two sequences with ``don't cares'' are of huge importance, yet the best known solution is an old dynamic programming approach that takes time quadratic in the length of the input. In social network analysis, it is common practice to determine the importance or centrality of different nodes in the network. However, for most of the centrality measures, the best known solution is to solve the classical all-pairs shortest paths problem, the fastest algorithm for which runs in essentially cubic time in the number of nodes. These quadratic and cubic time solutions are unsatisfactory, and no lower bounds are known, except in special models of computation. How do we explain the lack of progress on these important problems?

Proving NP-hardness is the now standard way to show that an efficient algorithm for a problem is unlikely. NP-hardness does not give an explicit lower bound. Instead, an NP-hard problem is believed to be hard because an efficient solution for it would imply efficient solutions for many problems that we do not believe can be solved efficiently. However, unless P=NP, NP-hardness cannot be used for problems already in polynomial time.

We propose to develop a theory similar to NP-hardness to address hardness within polynomial time. The approach we take is to design more refined reductions between problems, relating the exponents of algorithm running times. For instance, consider the CNF-SAT problem for Boolean formulas on n variables. It is a major open problem whether there is an algorithm that substantially beats the trivial 2^n solution that tries all possible assignments to the variables.

The Strong Exponential Time Hypothesis (SETH) states that there is no 2^{(1-eps)n} time algorithm for CNF-SAT for any eps>0. We develop reductions from CNF-SAT to problems such as graph diameter in sparse graphs, and longest common substring with don't cares, showing that if any of these problems have N^{2-eps} time algorithms for some eps>0, then there is a 2^{(1-eps')n} time algorithm for CNF-SAT for eps'>0, and hence the SETH is false. Thus, we can say that diameter and longest substring with don't cares are hard because CNF-SAT is hard.

This type of reduction can be used to also prove equivalences between problems in polynomial time. For instance, we show that computing many graph parameters (e.g. the radius, or the girth, or the Wiener index) are equivalent to computing APSP, in the sense that a subcubic algorithm for any of these problems implies a subcubic algorithm for all of them. A surprising consequence is that being able to compute a single number about a graph is the same as computing all pairwise distances! We prove such equivalences between APSP and a large collection of problems, including many graph centrality measures. The same approach also yields equivalences around other problems such as 3SUM and matrix multiplication, uncovering more structure in the world of low-polynomial time.

Bio:

Virginia Vassilevska Williams is currently an assistant professor of computer science at Stanford University. She received her Ph.D. from Carnegie Mellon University in 2008. She held several positions before joining Stanford. In the 2008-2009 academic year she was a member of the Institute for Advanced Study. Between 2009 and 2011 she was a postdoc at the computer science department at UC Berkeley supported by a Computing Innovations Fellowship. Between 2011 and 2013 she was an assistant research engineer at UC Berkeley and a research associate at Stanford. Her research is broadly in the design and analysis of algorithms, focusing on problems in graphs (such as shortest paths) and matrices (such as computing matrix products). She also has an interest in computational social choice.