VWVirginia Vassilevska Williams
Virginia Vassilevska Williams
*This is an algorithmically generated author record based on publicly available information.
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Virginia Vassilevska Williams has a total of 11 co-authors. Here are the top co-authors by number of shared publications:
- Amir Abboud
Weizmann Institute of Science, Rehovot, Israel
5 shared publications - Arturs Backurs
Stanford University Stanford University
2 shared publications - Aran Nayebi
Stanford University
1 shared publication - Fabrizio Grandoni
IDSIA, USI-SUPSI, Lugano, Switzerland
1 shared publication - Greg Bodwin
IDSIA USI-SUPSI
1 shared publication - Joshua Wang
Stanford University Stanford University
1 shared publication
Latest Publications
- Open Access
Preserving Distances in Very Faulty Graphs
Preservers and additive spanners are sparse (hence cheap to store) subgraphs that preserve the distances between given pairs of nodes exactly or with some small additive error, respectively. Since real-world networks are prone to failures, it makes sense to study fault-tolerant versions of the above structures. This turns out to be a surprisingly difficult task. For every small but arbitrary set of edge or vertex failures, the preservers and spanners need to contain {\em replacement paths} around the faulted set. In this paper we make substantial progress on fault tolerant preservers and additive spanners: (1) We present the first truly sub-quadratic size single-pair preservers in unweighted (possibly directed) graphs for \emph{any} fixed number $f$ of faults. Our result indeed generalizes to the single-source case, and can be used to build new fault-tolerant additive spanners (for all pairs). (2) The size of the above single-pair preservers is $O(n^{2-g(f)})$ for some positive function $g$, and grows to $O(n^2)$ for increasing $f$. We show that this is necessary even in undirected unweighted graphs, and even if you allow for a small additive error: If you aim at size $O(n^{2-\epsilon})$ for $\epsilon>0$, then the additive error has to be $\Omega(\eps f)$. This surprisingly matches known upper bounds in the literature. (3) For weighted graphs, we provide matching upper and lower bounds for the single pair case. Namely, the size of the preserver is $\Theta(n^2)$ for $f\geq 2$ in both directed and undirected graphs, while for $f=1$ the size is $\Theta(n)$ in undirected graphs. For directed graphs, we have a superlinear upper bound and a matching lower bound. Most of our lower bounds extend to the distance oracle setting, where rather than a subgraph we ask for any compact data structure.Open AccessPreserving Distances in Very Faulty Graphs
Preservers and additive spanners are sparse (hence cheap to store) subgraphs that preserve the distances between given pairs of nodes exactly or with some small additive error, respectively. Since real-world networks are prone to failures, it makes sense to study fault-tolerant versions of the above structures. This turns out to be a surprisingly difficult task. For every small but arbitrary set of edge or vertex failures, the preservers and spanners need to contain {\em replacement paths} around the faulted set. In this paper we make substantial progress on fault tolerant preservers and additive spanners: (1) We present the first truly sub-quadratic size single-pair preservers in unweighted (possibly directed) graphs for \emph{any} fixed number $f$ of faults. Our result indeed generalizes to the single-source case, and can be used to build new fault-tolerant additive spanners (for all pairs). (2) The size of the above single-pair preservers is $O(n^{2-g(f)})$ for some positive function $g$, and grows to $O(n^2)$ for increasing $f$. We show that this is necessary even in undirected unweighted graphs, and even if you allow for a small additive error: If you aim at size $O(n^{2-\epsilon})$ for $\epsilon>0$, then the additive error has to be $\Omega(\eps f)$. This surprisingly matches known upper bounds in the literature. (3) For weighted graphs, we provide matching upper and lower bounds for the single pair case. Namely, the size of the preserver is $\Theta(n^2)$ for $f\geq 2$ in both directed and undirected graphs, while for $f=1$ the size is $\Theta(n)$ in undirected graphs. For directed graphs, we have a superlinear upper bound and a matching lower bound. Most of our lower bounds extend to the distance oracle setting, where rather than a subgraph we ask for any compact data structure. - Open Access
Simulating Branching Programs with Edit Distance and Friends or: A Polylog Shaved is a Lower Bound Made
A recent and active line of work achieves tight lower bounds for fundamental problems under the Strong Exponential Time Hypothesis (SETH). A celebrated result of Backurs and Indyk (STOC'15) proves that the Edit Distance of two sequences of length n cannot be computed in strongly subquadratic time under SETH. The result was extended by follow-up works to simpler looking problems like finding the Longest Common Subsequence (LCS). SETH is a very strong assumption, asserting that even linear size CNF formulas cannot be analyzed for satisfiability with an exponential speedup over exhaustive search. We consider much safer assumptions, e.g. that such a speedup is impossible for SAT on much more expressive representations, like NC circuits. Intuitively, this seems much more plausible: NC circuits can implement complex cryptographic primitives, while CNFs cannot even approximately compute an XOR of bits. Our main result is a surprising reduction from SAT on Branching Programs to fundamental problems in P like Edit Distance, LCS, and many others. Truly subquadratic algorithms for these problems therefore have consequences that we consider to be far more remarkable than merely faster CNF SAT algorithms. For example, SAT on arbitrary o(n)-depth bounded fan-in circuits (and therefore also NC-Circuit-SAT) can be solved in (2-eps)^n time. A very interesting feature of our work is that we can prove major consequences even from mildly subquadratic algorithms for Edit Distance or LCS. For example, we show that if we can shave an arbitrarily large polylog factor from n^2 for Edit Distance then NEXP does not have non-uniform NC^1 circuits. A more fine-grained examination shows that even shaving a $\log^c{n}$ factor, for a specific constant $c \approx 10^3$, already implies new circuit lower bounds.Open AccessSimulating Branching Programs with Edit Distance and Friends or: A Polylog Shaved is a Lower Bound Made
A recent and active line of work achieves tight lower bounds for fundamental problems under the Strong Exponential Time Hypothesis (SETH). A celebrated result of Backurs and Indyk (STOC'15) proves that the Edit Distance of two sequences of length n cannot be computed in strongly subquadratic time under SETH. The result was extended by follow-up works to simpler looking problems like finding the Longest Common Subsequence (LCS). SETH is a very strong assumption, asserting that even linear size CNF formulas cannot be analyzed for satisfiability with an exponential speedup over exhaustive search. We consider much safer assumptions, e.g. that such a speedup is impossible for SAT on much more expressive representations, like NC circuits. Intuitively, this seems much more plausible: NC circuits can implement complex cryptographic primitives, while CNFs cannot even approximately compute an XOR of bits. Our main result is a surprising reduction from SAT on Branching Programs to fundamental problems in P like Edit Distance, LCS, and many others. Truly subquadratic algorithms for these problems therefore have consequences that we consider to be far more remarkable than merely faster CNF SAT algorithms. For example, SAT on arbitrary o(n)-depth bounded fan-in circuits (and therefore also NC-Circuit-SAT) can be solved in (2-eps)^n time. A very interesting feature of our work is that we can prove major consequences even from mildly subquadratic algorithms for Edit Distance or LCS. For example, we show that if we can shave an arbitrarily large polylog factor from n^2 for Edit Distance then NEXP does not have non-uniform NC^1 circuits. A more fine-grained examination shows that even shaving a $\log^c{n}$ factor, for a specific constant $c \approx 10^3$, already implies new circuit lower bounds. - Open Access
If the Current Clique Algorithms are Optimal, so is Valiant's Parser
The CFG recognition problem is: given a context-free grammar $\mathcal{G}$ and a string $w$ of length $n$, decide if $w$ can be obtained from $\mathcal{G}$. This is the most basic parsing question and is a core computer science problem. Valiant's parser from 1975 solves the problem in $O(n^{\omega})$ time, where $\omega<2.373$ is the matrix multiplication exponent. Dozens of parsing algorithms have been proposed over the years, yet Valiant's upper bound remains unbeaten. The best combinatorial algorithms have mildly subcubic $O(n^3/\log^3{n})$ complexity. Lee (JACM'01) provided evidence that fast matrix multiplication is needed for CFG parsing, and that very efficient and practical algorithms might be hard or even impossible to obtain. Lee showed that any algorithm for a more general parsing problem with running time $O(|\mathcal{G}|\cdot n^{3-\varepsilon})$ can be converted into a surprising subcubic algorithm for Boolean Matrix Multiplication. Unfortunately, Lee's hardness result required that the grammar size be $|\mathcal{G}|=\Omega(n^6)$. Nothing was known for the more relevant case of constant size grammars. In this work, we prove that any improvement on Valiant's algorithm, even for constant size grammars, either in terms of runtime or by avoiding the inefficiencies of fast matrix multiplication, would imply a breakthrough algorithm for the $k$-Clique problem: given a graph on $n$ nodes, decide if there are $k$ that form a clique. Besides classifying the complexity of a fundamental problem, our reduction has led us to similar lower bounds for more modern and well-studied cubic time problems for which faster algorithms are highly desirable in practice: RNA Folding, a central problem in computational biology, and Dyck Language Edit Distance, answering an open question of Saha (FOCS'14).Open AccessIf the Current Clique Algorithms are Optimal, so is Valiant's Parser
The CFG recognition problem is: given a context-free grammar $\mathcal{G}$ and a string $w$ of length $n$, decide if $w$ can be obtained from $\mathcal{G}$. This is the most basic parsing question and is a core computer science problem. Valiant's parser from 1975 solves the problem in $O(n^{\omega})$ time, where $\omega<2.373$ is the matrix multiplication exponent. Dozens of parsing algorithms have been proposed over the years, yet Valiant's upper bound remains unbeaten. The best combinatorial algorithms have mildly subcubic $O(n^3/\log^3{n})$ complexity. Lee (JACM'01) provided evidence that fast matrix multiplication is needed for CFG parsing, and that very efficient and practical algorithms might be hard or even impossible to obtain. Lee showed that any algorithm for a more general parsing problem with running time $O(|\mathcal{G}|\cdot n^{3-\varepsilon})$ can be converted into a surprising subcubic algorithm for Boolean Matrix Multiplication. Unfortunately, Lee's hardness result required that the grammar size be $|\mathcal{G}|=\Omega(n^6)$. Nothing was known for the more relevant case of constant size grammars. In this work, we prove that any improvement on Valiant's algorithm, even for constant size grammars, either in terms of runtime or by avoiding the inefficiencies of fast matrix multiplication, would imply a breakthrough algorithm for the $k$-Clique problem: given a graph on $n$ nodes, decide if there are $k$ that form a clique. Besides classifying the complexity of a fundamental problem, our reduction has led us to similar lower bounds for more modern and well-studied cubic time problems for which faster algorithms are highly desirable in practice: RNA Folding, a central problem in computational biology, and Dyck Language Edit Distance, answering an open question of Saha (FOCS'14). - Open Access
A 7/3-Approximation for Feedback Vertex Sets in Tournaments
We consider the minimum-weight feedback vertex set problem in tournaments: given a tournament with non-negative vertex weights, remove a minimum-weight set of vertices that intersects all cycles. This problem is $\mathsf{NP}$-hard to solve exactly, and Unique Games-hard to approximate by a factor better than 2. We present the first $7/3$ approximation algorithm for this problem, improving on the previously best known ratio $5/2$ given by Cai et al. [FOCS 1998, SICOMP 2001].Open AccessA 7/3-Approximation for Feedback Vertex Sets in Tournaments
We consider the minimum-weight feedback vertex set problem in tournaments: given a tournament with non-negative vertex weights, remove a minimum-weight set of vertices that intersects all cycles. This problem is $\mathsf{NP}$-hard to solve exactly, and Unique Games-hard to approximate by a factor better than 2. We present the first $7/3$ approximation algorithm for this problem, improving on the previously best known ratio $5/2$ given by Cai et al. [FOCS 1998, SICOMP 2001]. - Open Access
Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter
The radius and diameter are fundamental graph parameters. They are defined as the minimum and maximum of the eccentricities in a graph, respectively, where the eccentricity of a vertex is the largest distance from the vertex to another node. In directed graphs, there are several versions of these problems. For instance, one may choose to define the eccentricity of a node in terms of the largest distance into the node, out of the node, the sum of the two directions (i.e. roundtrip) and so on. All versions of diameter and radius can be solved via solving all-pairs shortest paths (APSP), followed by a fast postprocessing step. Solving APSP, however, on $n$-node graphs requires $\Omega(n^2)$ time even in sparse graphs, as one needs to output $n^2$ distances. Motivated by known and new negative results on the impossibility of computing these measures exactly in general graphs in truly subquadratic time, under plausible assumptions, we search for \emph{approximation} and \emph{fixed parameter subquadratic} algorithms, and for reasons why they do not exist. Our results include: - Truly subquadratic approximation algorithms for most of the versions of Diameter and Radius with \emph{optimal} approximation guarantees (given truly subquadratic time), under plausible assumptions. In particular, there is a $2$-approximation algorithm for directed Radius with one-way distances that runs in $\tilde{O}(m\sqrt{n})$ time, while a $(2-\delta)$-approximation algorithm in $O(n^{2-\epsilon})$ time is unlikely. - On graphs with treewidth $k$, we can solve the problems in $2^{O(k\log{k})}n^{1+o(1)}$ time. We show that these algorithms are near optimal since even a $(3/2-\delta)$-approximation algorithm that runs in time $2^{o(k)}n^{2-\epsilon}$ would refute the plausible assumptions.Open AccessApproximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter
The radius and diameter are fundamental graph parameters. They are defined as the minimum and maximum of the eccentricities in a graph, respectively, where the eccentricity of a vertex is the largest distance from the vertex to another node. In directed graphs, there are several versions of these problems. For instance, one may choose to define the eccentricity of a node in terms of the largest distance into the node, out of the node, the sum of the two directions (i.e. roundtrip) and so on. All versions of diameter and radius can be solved via solving all-pairs shortest paths (APSP), followed by a fast postprocessing step. Solving APSP, however, on $n$-node graphs requires $\Omega(n^2)$ time even in sparse graphs, as one needs to output $n^2$ distances. Motivated by known and new negative results on the impossibility of computing these measures exactly in general graphs in truly subquadratic time, under plausible assumptions, we search for \emph{approximation} and \emph{fixed parameter subquadratic} algorithms, and for reasons why they do not exist. Our results include: - Truly subquadratic approximation algorithms for most of the versions of Diameter and Radius with \emph{optimal} approximation guarantees (given truly subquadratic time), under plausible assumptions. In particular, there is a $2$-approximation algorithm for directed Radius with one-way distances that runs in $\tilde{O}(m\sqrt{n})$ time, while a $(2-\delta)$-approximation algorithm in $O(n^{2-\epsilon})$ time is unlikely. - On graphs with treewidth $k$, we can solve the problems in $2^{O(k\log{k})}n^{1+o(1)}$ time. We show that these algorithms are near optimal since even a $(3/2-\delta)$-approximation algorithm that runs in time $2^{o(k)}n^{2-\epsilon}$ would refute the plausible assumptions. - Open Access
Quadratic-Time Hardness of LCS and other Sequence Similarity Measures
Two important similarity measures between sequences are the longest common subsequence (LCS) and the dynamic time warping distance (DTWD). The computations of these measures for two given sequences are central tasks in a variety of applications. Simple dynamic programming algorithms solve these tasks in $O(n^2)$ time, and despite an extensive amount of research, no algorithms with significantly better worst case upper bounds are known. In this paper, we show that an $O(n^{2-\epsilon})$ time algorithm, for some $\epsilon>0$, for computing the LCS or the DTWD of two sequences of length $n$ over a constant size alphabet, refutes the popular Strong Exponential Time Hypothesis (SETH). Moreover, we show that computing the LCS of $k$ strings over an alphabet of size $O(k)$ cannot be done in $O(n^{k-\epsilon})$ time, for any $\epsilon>0$, under SETH. Finally, we also address the time complexity of approximating the DTWD of two strings in truly subquadratic time.Open AccessQuadratic-Time Hardness of LCS and other Sequence Similarity Measures
Two important similarity measures between sequences are the longest common subsequence (LCS) and the dynamic time warping distance (DTWD). The computations of these measures for two given sequences are central tasks in a variety of applications. Simple dynamic programming algorithms solve these tasks in $O(n^2)$ time, and despite an extensive amount of research, no algorithms with significantly better worst case upper bounds are known. In this paper, we show that an $O(n^{2-\epsilon})$ time algorithm, for some $\epsilon>0$, for computing the LCS or the DTWD of two sequences of length $n$ over a constant size alphabet, refutes the popular Strong Exponential Time Hypothesis (SETH). Moreover, we show that computing the LCS of $k$ strings over an alphabet of size $O(k)$ cannot be done in $O(n^{k-\epsilon})$ time, for any $\epsilon>0$, under SETH. Finally, we also address the time complexity of approximating the DTWD of two strings in truly subquadratic time. - Open Access
Quantum algorithms for shortest paths problems in structured instances
We consider the quantum time complexity of the all pairs shortest paths (APSP) problem and some of its variants. The trivial classical algorithm for APSP and most all pairs path problems runs in $O(n^3)$ time, while the trivial algorithm in the quantum setting runs in $\tilde{O}(n^{2.5})$ time, using Grover search. A major open problem in classical algorithms is to obtain a truly subcubic time algorithm for APSP, i.e. an algorithm running in $O(n^{3-\varepsilon})$ time for constant $\varepsilon>0$. To approach this problem, many truly subcubic time classical algorithms have been devised for APSP and its variants for structured inputs. Some examples of such problems are APSP in geometrically weighted graphs, graphs with small integer edge weights or a small number of weights incident to each vertex, and the all pairs earliest arrivals problem. In this paper we revisit these problems in the quantum setting and obtain the first nontrivial (i.e. $O(n^{2.5-\varepsilon})$ time) quantum algorithms for the problems.Open AccessQuantum algorithms for shortest paths problems in structured instances
We consider the quantum time complexity of the all pairs shortest paths (APSP) problem and some of its variants. The trivial classical algorithm for APSP and most all pairs path problems runs in $O(n^3)$ time, while the trivial algorithm in the quantum setting runs in $\tilde{O}(n^{2.5})$ time, using Grover search. A major open problem in classical algorithms is to obtain a truly subcubic time algorithm for APSP, i.e. an algorithm running in $O(n^{3-\varepsilon})$ time for constant $\varepsilon>0$. To approach this problem, many truly subcubic time classical algorithms have been devised for APSP and its variants for structured inputs. Some examples of such problems are APSP in geometrically weighted graphs, graphs with small integer edge weights or a small number of weights incident to each vertex, and the all pairs earliest arrivals problem. In this paper we revisit these problems in the quantum setting and obtain the first nontrivial (i.e. $O(n^{2.5-\varepsilon})$ time) quantum algorithms for the problems. - Open Access
Popular conjectures imply strong lower bounds for dynamic problems
We consider several well-studied problems in dynamic algorithms and prove that sufficient progress on any of them would imply a breakthrough on one of five major open problems in the theory of algorithms: 1. Is the 3SUM problem on $n$ numbers in $O(n^{2-\epsilon})$ time for some $\epsilon>0$? 2. Can one determine the satisfiability of a CNF formula on $n$ variables in $O((2-\epsilon)^n poly n)$ time for some $\epsilon>0$? 3. Is the All Pairs Shortest Paths problem for graphs on $n$ vertices in $O(n^{3-\epsilon})$ time for some $\epsilon>0$? 4. Is there a linear time algorithm that detects whether a given graph contains a triangle? 5. Is there an $O(n^{3-\epsilon})$ time combinatorial algorithm for $n\times n$ Boolean matrix multiplication? The problems we consider include dynamic versions of bipartite perfect matching, bipartite maximum weight matching, single source reachability, single source shortest paths, strong connectivity, subgraph connectivity, diameter approximation and some nongraph problems such as Pagh's problem defined in a recent paper by Patrascu [STOC 2010].Open AccessPopular conjectures imply strong lower bounds for dynamic problems
We consider several well-studied problems in dynamic algorithms and prove that sufficient progress on any of them would imply a breakthrough on one of five major open problems in the theory of algorithms: 1. Is the 3SUM problem on $n$ numbers in $O(n^{2-\epsilon})$ time for some $\epsilon>0$? 2. Can one determine the satisfiability of a CNF formula on $n$ variables in $O((2-\epsilon)^n poly n)$ time for some $\epsilon>0$? 3. Is the All Pairs Shortest Paths problem for graphs on $n$ vertices in $O(n^{3-\epsilon})$ time for some $\epsilon>0$? 4. Is there a linear time algorithm that detects whether a given graph contains a triangle? 5. Is there an $O(n^{3-\epsilon})$ time combinatorial algorithm for $n\times n$ Boolean matrix multiplication? The problems we consider include dynamic versions of bipartite perfect matching, bipartite maximum weight matching, single source reachability, single source shortest paths, strong connectivity, subgraph connectivity, diameter approximation and some nongraph problems such as Pagh's problem defined in a recent paper by Patrascu [STOC 2010].