Arrow Research search

Author name cluster

Virginia Vassilevska Williams

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

69 papers
2 author rows

Possible papers

69

STOC Conference 2025 Conference Paper

All-Pairs Shortest Paths with Few Weights per Node

  • Amir Abboud
  • Nick Fischer
  • Ce Jin 0001
  • Virginia Vassilevska Williams
  • Zoe Xi

We study the central All-Pairs Shortest Paths (APSP) problem under the restriction that there are at most d distinct weights on the outgoing edges from every node. For d = n this is the classical (unrestricted) APSP problem that is hypothesized to require cubic time n 3− o (1) , and at the other extreme, for d =1, it is equivalent to the Node-Weighted APSP problem. We present new algorithms that achieve the following results: * Node-Weighted APSP can be solved in time Õ( n (3+ω)/2 ) = Õ( n 2.686 ), improving on the 15-year-old subcubic bounds Õ( n (9+ω)/4 ) = Õ( n 2.843 ) [Chan; STOC ’07] and Õ( n 2.830 ) [Yuster; SODA ’09]. This positively resolves the question of whether Node-Weighted APSP is an ”intermediate” problem in the sense of having complexity n 2.5+ o (1) if ω=2, in which case it also matches an n 2.5− o (1) conditional lower bound. * For up to d ≤ n 3−ω−є distinct weights per node (where є > 0), the problem can be solved in subcubic time O ( n 3− f (є) ) (where f (є) > 0). In particular, assuming that ω = 2, we can tolerate any sublinear number of distinct weights per node d ≤ n 1−є , whereas previous work [Yuster; SODA ’09] could only handle d ≤ n 1/2−є in subcubic time. This promotes our understanding of the APSP hypothesis showing that the hardest instances must exhaust a linear number of weights per node. With the current bounds on ω, we achieve a subcubic algorithm for d ≤ n 0.628 whereas previously a subcubic running time could only be achieved for d ≤ n 0.384 . Our result also applies to the All-Pairs Exact Triangle problem, thus generalizing a result of Chan and Lewenstein on “Clustered 3SUM” from arrays to matrices. Notably, our technique constitutes a rare application of additive combinatorics in graph algorithms. We complement our algorithmic results with simple hardness reductions extending the n 2.5− o (1) conditional lower bound for Node-Weighted APSP to undirected graphs. Interestingly, under fine-grained assumptions, the complexity in the undirected case jumps from O ( n ω ) for d =1 to n 2.5− o (1) for d ≥ 2.

Details

STOC Conference 2025 Conference Paper

Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence

  • Jakob Nogler
  • Adam Polak 0001
  • Barna Saha
  • Virginia Vassilevska Williams
  • Yinzhan Xu
  • Christopher Ye 0001

The tree edit distance (TED) between two rooted ordered trees with n nodes labeled from an alphabet Σ is the minimum cost of transforming one tree into the other by a sequence of valid operations consisting of insertions, deletions and relabeling of nodes. The tree edit distance is a well-known generalization of string edit distance and has been studied since the 1970s. Its running time has seen steady improvements starting with an O ( n 6 ) algorithm [Tai, J.ACM 1979], improved to O ( n 4 ) [Shasha, Zhang, SICOMP 1989] and to O ( n 3 log n ) [Klein, ESA 1998], and culminating in an O ( n 3 ) algorithm [Demaine, Mozes, Rossman, Weimann, ACM TALG 2010]. The latter is known to be optimal for any dynamic programming based algorithm that falls under a certain decomposition framework that captures all known sub- n 4 time algorithms. Fine-grained complexity casts further light onto this hardness showing that a truly subcubic time algorithm for TED implies a truly subcubic time algorithm for All-Pairs Shortest Paths (APSP) [Bringmann, Gawrychowski, Mozes, Weimann, ACM TALG 2020]. Therefore, under the popular APSP hypothesis, a truly subcubic time algorithm for TED cannot exist. However, unlike many problems in fine-grained complexity for which conditional hardness based on APSP also comes with equivalence to APSP, whether TED can be reduced to APSP has remained unknown. In this paper, we resolve this. Not only we show that TED is fine-grained equivalent to APSP, our reduction is tight enough, so that combined with the fastest APSP algorithm to-date [Williams, SICOMP 2018] it gives the first ever subcubic time algorithm for TED running in n 3 /2 Ω(√log n ) time. We also consider the unweighted tree edit distance problem in which the cost of each edit (insertion, deletion, and relabeling) is one. For unweighted TED, a truly subcubic algorithm is known due to Mao [Mao, FOCS 2022], and later improved slightly by Dürr [Dürr, IPL 2023] to run in O ( n 2.9148 ) time. Since their algorithm uses bounded monotone min-plus product as a crucial subroutine, and the best running time for this product is Õ( n 3+ω/2 )≤ O ( n 2.6857 ) (where ω is the exponent of fast matrix multiplication), the much higher running time of unweighted TED remained unsatisfactory. In this work, we close this gap and give an algorithm for unweighted TED that runs in Õ( n 3+ω/2 ) time.

Details

MFCS Conference 2025 Conference Paper

Shortest Paths in Multimode Graphs

  • Yael Kirkpatrick
  • Virginia Vassilevska Williams

In this work we study shortest path problems in multimode graphs, a generalization of the min-distance measure introduced by Abboud, Vassilevska W. and Wang in [SODA'16]. A multimode shortest path is the shortest path using one of multiple "modes" of transportation that cannot be combined. This represents real-world scenarios where different modes are not combinable, such as flights operated by different airline alliances. The problem arises naturally in machine learning in the context of learning with multiple embedding. More precisely, a k-multimode graph is a collection of k graphs on the same vertex set and the k-mode distance between two vertices is defined as the minimum among the distances computed in each individual graph. We focus on approximating fundamental graph parameters on these graphs, specifically diameter and radius. In undirected multimode graphs we first show an elegant linear time 3-approximation algorithm for 2-mode diameter. We then extend this idea into a general subroutine that can be used as a part of any α-approximation, and use it to construct a 2 and 2. 5 approximation algorithm for 2-mode diameter. For undirected radius, we introduce a general scheme that can compute a 3-approximation of the k-mode radius for any k and runs in near linear time in the case of k = O(1). In the directed case we establish an equivalence between approximating 2-mode diameter on DAGs and approximating the min-diameter, while for general graphs we develop novel techniques and provide a linear time algorithm to determine whether the diameter is finite. We also develop many conditional fine-grained lower bounds for various multimode diameter and radius approximation problems. We are able to show that many of our algorithms are tight under popular fine-grained complexity hypotheses, including our linear time 3-approximation for 3-mode undirected diameter and radius. As part of this effort we propose the first extension to the Hitting Set Hypothesis [SODA'16], which we call the 𝓁-Hitting Set Hypothesis. We use this hypothesis to prove the first parameterized lower bound tradeoff for radius approximation algorithms.

Details

SODA Conference 2024 Conference Paper

New Bounds for Matrix Multiplication: from Alpha to Omega

  • Virginia Vassilevska Williams
  • Yinzhan Xu
  • Zixuan Xu
  • Renfei Zhou

The main contribution of this paper is a new improved variant of the laser method for designing matrix multiplication algorithms. Building upon the recent techniques of [Duan, Wu, Zhou, FOCS 2023], the new method introduces several new ingredients that not only yield an improved bound on the matrix multiplication exponent ω, but also improve the known bounds on rectangular matrix multiplication by [Le Gall and Urrutia, SODA 2018]. In particular, the new bound on ω is ω ≤ 2. 371552 (improved from ω ≤ 2. 371866). For the dual matrix multiplication exponent α defined as the largest α for which ω(1, α, 1) = 2, we obtain the improvement α ≥ 0. 321334 (improved from α ≥ 0. 31389). Similar improvements are obtained for various other exponents for multiplying rectangular matrices.

Details

SODA Conference 2024 Conference Paper

Simpler and Higher Lower Bounds for Shortcut Sets

  • Virginia Vassilevska Williams
  • Yinzhan Xu
  • Zixuan Xu

We study the well-known shortcut set problem: how much can one decrease the diameter of a directed graph by adding a small set of shortcuts from the transitive closure of the graph. We provide a variety of lower bounds. First, we vastly simplify the recent construction of Bodwin and Hoppenworth [FOCS 2023] which showed an lower bound for the diameter of a directed unweighted n -node graph after adding O(n) shortcut edges. We highlight that our simplification completely removes the use of the convex sets by Bárány and Larman [Math. Ann. 1998] used in all previous lower bound constructions. Our simplification also removes the need for randomness and further removes some log factors. It allows us to generalize the construction to higher dimensions, which in turn can be used to show the following results: • There is an Ω( n 1/5 ) lower bound for the diameter of the graph after adding O(m) shortcuts, where m denotes the number of edges in the input graph. • For all ɛ > 0, there exists a δ > 0 such that there are n -vertex O ( n )-edge graphs G where adding any shortcut set of size O(n 2-ɛ ) keeps the diameter of G at Ω( n δ ). This improves the sparsity of the constructed graph compared to a known similar result by Hesse [SODA 2003]. • For any integer d ≥ 2, there exists a graph G = ( V, E ) on n vertices and S ⊆ V with, such that when adding O ( n ) or O ( m ) shortcuts, the sourcewise diameter (the largest distance from some vertex in S to some reachable vertex in the graph) is. This initiates the study of sourcewise diameter in the setting of the shortcut set problem; previously, the study of the sourcewise variant is popular in a wide variety of related problems such as spanners and distance preservers. Complementing this lower bound result, we also provide an upper bound: we show that, we can reduce the sourcewise diameter to by adding O ( n ) shortcut edges. * Massachusetts Institute of Technology. Supported by NSF Grants CCF-2129139 and CCF-2330048 and BSF Grant 2020356.

Details

STOC Conference 2024 Conference Paper

Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques

  • Mina Dalirrooyfard
  • Surya Mathialagan
  • Virginia Vassilevska Williams
  • Yinzhan Xu

We study the problem of finding and listing k -cliques in an m -edge, n -vertex graph, for constant k ≥ 3. This is a fundamental problem of both theoretical and practical importance. Our first contribution is an algorithmic framework for finding k -cliques that gives the first improvement in 19 years over the old runtimes for 4 and 5-clique finding, as a function of m [Eisenbrand and Grandoni, TCS’04]. With the current bounds on matrix multiplication, our algorithms run in O ( m 1.66 ) and O ( m 2.06 ) time, respectively, for 4-clique and 5-clique finding. Our main contribution is an output-sensitive algorithm for listing k -cliques, for any constant k ≥ 3. We complement the algorithm with tight lower bounds based on standard fine-grained assumptions. Previously, the only known conditionally optimal output-sensitive algorithms were for the case of 3-cliques given by Bj'orklund, Pagh, Vassilevska W. and Zwick [ICALP’14]. If the matrix multiplication exponent ω is 2, and if the number of k -cliques t is large enough, the running time of our algorithms is Õ(min{ m 1/ k −2 t 1 − 2/ k ( k −2) , n 2/ k −1 t 1−2/ k ( k −1) }), and this is tight under the Exact- k -Clique Hypothesis. This running time naturally extends the running time obtained by Bj'orklund, Pagh, Vassilevska W. and Zwick for k =3. Our framework is very general in that it gives k -clique listing algorithms whose running times can be measured in terms of the number of ℓ-cliques Δ ℓ in the graph for any 1≤ ℓ< k . This generalizes the typical parameterization in terms of n (the number of 1-cliques) and m (the number of 2-cliques). If ω is 2, and if the size of the output, Δ k , is sufficiently large, then for every ℓ< k , the running time of our algorithm for listing k -cliques is Õ(Δ ℓ 2/ℓ ( k − ℓ) Δ k 1−2/ k ( k −ℓ) ). We also show that this runtime is optimal for all 1 ≤ ℓ < k under the Exact k -Clique hypothesis.

Details

FOCS Conference 2023 Conference Paper

Faster Algorithms for Text-to-Pattern Hamming Distances

  • Timothy M. Chan
  • Ce Jin 0001
  • Virginia Vassilevska Williams
  • Yinzhan Xu

We study the classic Text-to-Pattern Hamming Distances problem: given a pattern P of length m and a text T of length n, both over a polynomial-size alphabet, compute the Hamming distance between P and $T[i \ldots i+m-1]$ for every shift i, under the standard Word-RAM model with $\Theta(\log n)$-bit words. •We provide an $O(n \sqrt{m})$ time Las Vegas randomized algorithm for this problem, beating the decades-old $O(n \sqrt{m \log m})$ running time [Abrahamson, SICOMP 1987]. We also obtain a deterministic algorithm, with a slightly higher $O\left(n \sqrt{m}(\log m \log \log m)^{1 / 4}\right)$ running time. Our randomized algorithm extends to the k-bounded setting, with running time $O\left(n+\frac{n k}{\sqrt{m}}\right)$, removing all the extra logarithmic factors from earlier algorithms [Gawrychowski and Uznanski, ICALP 2018; Chan, Golan, Kociumaka, Kopelowitz and Porat, STOC 2020]. •For the $(1+\varepsilon)$-approximate version of Text-to-Pattern Hamming Distances, we give an $\widetilde{O}\left(\varepsilon^{-0. 93} n\right)$ time Monte Carlo randomized algorithm (where $\widetilde{O}$ hides poly-logarithmic factors), beating the previous $\widetilde{O}\left(\varepsilon^{-1} n\right)$ running time [Kopelowitz and Porat, FOCS 2015; Kopelowitz and Porat, SOSA 2018]. Our approximation algorithm exploits a connection with 3SUM, and uses a combination of Fredman’s trick, equality matrix product, and random sampling; in particular, we obtain new results on approximate counting versions of 3 SUM and Exact Triangle, which may be of independent interest. Our exact algorithms use a novel combination of hashing, bit-packed FFT, and recursion; in particular, we obtain a faster algorithm for computing the sumset of two integer sets, in the regime when the universe size is close to quadratic in the number of elements. We also prove a fine-grained equivalence between the exact Text-to-Pattern Hamming Distances problem and a range-restricted, counting version of 3 SUM.

Details

STOC Conference 2023 Conference Paper

Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More

  • Timothy M. Chan
  • Virginia Vassilevska Williams
  • Yinzhan Xu

In this paper we carefully combine Fredman’s trick [SICOMP’76] and Matoušek’s approach for dominance product [IPL’91] to obtain powerful results in fine-grained complexity. Under the hypothesis that APSP for undirected graphs with edge weights in {1, 2, …, n } requires n 3− o (1) time (when ω=2), we show a variety of conditional lower bounds, including an n 7/3− o (1) lower bound for unweighted directed APSP and an n 2.2− o (1) lower bound for computing the Minimum Witness Product between two n × n Boolean matrices, even if ω=2, improving upon their trivial n 2 lower bounds. Our techniques can also be used to reduce the unweighted directed APSP problem to other problems. In particular, we show that (when ω = 2), if unweighted directed APSP requires n 2.5− o (1) time, then Minimum Witness Product requires n 7/3− o (1) time. We show that, surprisingly, many central problems in fine-grained complexity are equivalent to their natural counting versions. In particular, we show that Min-Plus Product and Exact Triangle are subcubically equivalent to their counting versions, and 3SUM is subquadratically equivalent to its counting version. We also obtain new algorithms using new variants of the Balog-Szemerédi-Gowers theorem from additive combinatorics. For example, we get an O ( n 3.83 ) time deterministic algorithm for exactly counting the number of shortest paths in an arbitrary weighted graph, improving the textbook O ( n 4 ) time algorithm. We also get faster algorithms for 3SUM in preprocessed universes, and deterministic algorithms for 3SUM on monotone sets in {1, 2, …, n } d .

Details

SODA Conference 2023 Conference Paper

Improved girth approximation in weighted undirected graphs

  • Avi Kadria
  • Liam Roditty
  • Aaron Sidford
  • Virginia Vassilevska Williams
  • Uri Zwick

Let G = ( V, E, ℓ) be a n -nodes m -edges weighted undirected graph, where ℓ: E → (0, ∞) is a real length function defined on its edges. Let g be the length of the shortest cycle in G. We present an algorithm that in O ( kn 1+1/ k log n + m(k + log n )) expected running time finds a cycle of length at most, for every integer k ≥ 1. This improves upon the previous best algorithm that in O((n 1+1/k log n + m ) log( nM )) time, where ℓ: E → [1, M ] is an integral length function, finds a cycle of length at most 2 kg [KRS + 22]. For k = 1 our algorithm also improves the result of Roditty and Tov [RT13].

Details

SODA Conference 2022 Conference Paper

Algorithmic trade-offs for girth approximation in undirected graphs

  • Avi Kadria
  • Liam Roditty
  • Aaron Sidford
  • Virginia Vassilevska Williams
  • Uri Zwick

We present several new efficient algorithms for approximating the girth, g, of weighted and unweighted n -vertex, m -edge undirected graphs. For undirected graphs with polynomially bounded, integer, non-negative edge weights, we provide an algorithm that for every integer k ≥ 1, runs in Õ ( m + n 1 + 1/ k log g ) time and returns a cycle of length at most 2 kg. For unweighted, undirected graphs we present an algorithm that for every k ≥ 1, runs in Õ ( n 1 + 1/ k ) time and returns a cycle of length at most 2 k [ g /2], an almost k -approximation. Both algorithms provide trade-offs between the running time and the quality of the approximation. We also obtain faster algorithms for approximation factors better than 2, and improved approximations when the girth is odd or small (e. g. , 3 and 4).

Details

FOCS Conference 2022 Conference Paper

Algorithms and Lower Bounds for Replacement Paths under Multiple Edge Failure

  • Virginia Vassilevska Williams
  • Eyob Woldeghebriel
  • Yinzhan Xu

This paper considers a natural fault-tolerant shortest paths problem: for some constant integer f, given a directed weighted graph with no negative cycles and two fixed vertices s and t, compute (either explicitly or implicitly) for every tuple of f edges, the distance from s to t if these edges fail. We call this problem f-Fault Replacement Paths (f FRP). We first present an $\tilde{O}(n^{3}$) time algorithm for 2FRP in n-vertex directed graphs with arbitrary edge weights and no negative cycles. As 2FRP is a generalization of the well-studied Replacement Paths problem (RP) that asks for the distances between s and t for any single edge failure, 2FRP is at least as hard as RP. Since RP in graphs with arbitrary weights is equivalent in a fine-grained sense to All-Pairs Shortest Paths (APSP) [Vassilevska Williams and Williams FOCS’10, J. ACM’18], 2FRP is at least as hard as APSP, and thus a substantially subcubic time algorithm in the number of vertices for 2FRP would be a breakthrough. Therefore, our algorithm in $\tilde{O}(n^{3})$ time is conditionally nearly optimal. Our algorithm immediately implies an $\tilde{O}(n^{f+1})$ time algorithm for the more general f FRP problem, giving the first improvement over the straightforward $O(n^{f+2})$ time algorithm. Then we focus on the restriction of 2FRP to graphs with small integer weights bounded by M in absolute values. We show that similar to $\mathrm{R}\mathrm{P}, 2\mathrm{F}\mathrm{R}\mathrm{P}$ has a substantially subcubic time algorithm for small enough M. Using the current best algorithms for rectangular matrix multiplication, we obtain a randomized algorithm that runs in $\tilde{O}(M^{2/3}n^{2. 9153})$ time. This immediately implies an improvement over our $\tilde{O}(n^{f+1})$ time arbitrary weight algorithm for all $f\gt1$. We also present a data structure variant of the algorithm that can trade off pre-processing and query time. In addition to the algebraic algorithms, we also give an $n^{8/3-o(1)}$ conditional lower bound for combinatorial 2FRP algorithms in directed unweighted graphs, and more generally, combinatorial lower bounds for the data structure version of $fF\mathrm{R}\mathrm{P}$.

Details

FOCS Conference 2022 Conference Paper

Approximation Algorithms and Hardness for n-Pairs Shortest Paths and All-Nodes Shortest Cycles

  • Mina Dalirrooyfard
  • Ce Jin 0001
  • Virginia Vassilevska Williams
  • Nicole Wein

We study the approximability of two related problems on graphs with n nodes and m edges: n-Pairs Shortest Paths (n-PSP), where the goal is to find a shortest path between O(n) prespecified pairs, and All Node Shortest Cycles (ANSC), where the goal is to find the shortest cycle passing through each node. Approximate n-PSP has been previously studied, mostly in the context of distance oracles. We ask the question of whether approximate n-PSP can be solved faster than by using distance oracles or All Pair Shortest Paths (APSP). ANSC has also been studied previously, but only in terms of exact algorithms, rather than approximation. We provide a thorough study of the approximability of n PSP and ANSC, providing a wide array of algorithms and conditional lower bounds that trade off between running time and approximation ratio. A highlight of our conditional lower bounds results is that for any integer k$\geq$1, under the combinatorial 4k-clique hypothesis, there is no combinatorial algorithm for unweighted undirected n-PSP with approximation ratio better than $1+1/k$ that runs in $O(m^{2-2/(k+1)}n^{1/(k+1)-\varepsilon})$ time. This nearly matches an upper bound implied by the result of Agarwal (2014). Our algorithms use a surprisingly wide range of techniques, including techniques from the girth problem, distance oracles, approximate APSP, spanners, fault-tolerant spanners, and link-cut trees. A highlight of our algorithmic results is that one can solve both n-PSP and ANSC in $O(m+n^{3/2+\in})$ time 1 with approximation factor $2+\varepsilon$ (and additive error that is function of $\varepsilon$), for any constant $\varepsilon\lt 0$. For n-PSP, our conditional lower bounds imply that this approximation ratio is nearly optimal for any subquadratic-time combinatorial algorithm. We further extend these algorithms for n-PSP and ANSC to obtain a time/accuracy trade-off that includes near-linear time algorithms. 1 $\tilde{O}$ hides sub-polynomial factors. Additionally, for ANSC, for all integers $k\geq 1$, we extend the very recent almost k-approximation algorithm for the girth problem that works in $\tilde{O}(n^{1+1/k})$ time [Kadria et al. SODA’22], and obtain an almost k-approximation algorithm for ANSC in $\tilde{O}(mn^{1/k})$ time.

Details

SODA Conference 2022 Conference Paper

Better Lower Bounds for Shortcut Sets and Additive Spanners via an Improved Alternation Product

  • Kevin Lu
  • Virginia Vassilevska Williams
  • Nicole Wein
  • Zixuan Xu

We obtain improved lower bounds for additive spanners, additive emulators, and diameter-reducing shortcut sets. Spanners and emulators are sparse graphs that approximately preserve the distances of a given graph. A shortcut set is a set of edges that when added to a directed graph, decreases its diameter. The previous best known lower bounds for these three structures are given by Huang and Pettie [HP18]. For O ( n )-sized spanners, we improve the lower bound on the additive stretch from Ω( n 1 / 11 ) to Ω( n 2 / 21 ). For O ( n )-sized emulators, we improve the lower bound on the additive stretch from Ω( n 1/18 ) to Ω( n 2/29 ). For O ( m )-sized shortcut sets, we improve the lower bound on the graph diameter from Ω( n 1/11 ) to Ω( n 1/8 ). Our key technical contribution, which is the basis of all of our bounds, is an improvement of a graph product known as an alternation product.

Details

STOC Conference 2022 Conference Paper

Hardness for triangle problems under even more believable hypotheses: reductions from real APSP, real 3SUM, and OV

  • Timothy M. Chan
  • Virginia Vassilevska Williams
  • Yinzhan Xu

The 3SUM hypothesis, the All-Pairs Shortest Paths (APSP) hypothesis and the Strong Exponential Time Hypothesis are the three main hypotheses in the area of fine-grained complexity. So far, within the area, the first two hypotheses have mainly been about integer inputs in the Word RAM model of computation. The “Real APSP” and “Real 3SUM” hypotheses, which assert that the APSP and 3SUM hypotheses hold for real-valued inputs in a reasonable version of the Real RAM model, are even more believable than their integer counterparts.

Details

FOCS Conference 2022 Conference Paper

Induced Cycles and Paths Are Harder Than You Think

  • Mina Dalirrooyfard
  • Virginia Vassilevska Williams

The goal of the paper is to give fine-grained hardness results for the Subgraph Isomorphism (SI) problem for fixed size induced patterns H, based on the k-Clique hypothesis that the current best algorithms for Clique are optimal. Our first main result is that for any pattern graph H that is a core, the SI problem for H is at least as hard as t-Clique, where t is the size of the largest clique minor of H. This improves (for cores) the previous known results [Dalirrooyfard-Vassilevska W. STOC’20] that the SI for H is at least as hard as k-clique where k is the size of the largest clique subgraph in H, or the chromatic number of H (under the Hadwiger conjecture). For detecting any graph pattern H, we further remove the dependency of the result of [Dalirrooyfard-Vassilevska W. STOC’20] on the Hadwiger conjecture at the cost of a sub-polynomial decrease in the lower bound. The result for cores allows us to prove that the SI problem for induced k-Path and k-Cycle is harder than previously known. Previously [Floderus et al. Theor. CS 2015] had shown that k-Path and k-Cycle are at least as hard to detect as a $\lfloor$k/2$\rfloor -$Clique. We show that they are in fact at least as hard as 3k/4-O(1)-Clique, improving the conditional lower bound exponent by a factor of 3/2. This shoivs for instance that the knoivn $O(n^{5})$ combinatorial algorithm for 7-cycle detection is conditionally tight. Finally, we provide a new conditional lower bound for detecting induced 4-cycles: $n^{2-o(1)}$ time is necessary even in graphs with n nodes and $O(n^{15})$ edges. The 4-cycle is the smallest induced pattern whose running time is not well-understood. It can be solved in matrix multiplication, $O(n^{\omega})$ time, but no conditional lower bounds were known until ours. We provide evidence that certain types of reductions from triangle detection to 4-Cycle would not be possible. We do this by studying a new problem called Paired Pattern Detection.

Details

IJCAI Conference 2022 Conference Paper

Near-Tight Algorithms for the Chamberlin-Courant and Thiele Voting Rules

  • Krzysztof Sornat
  • Virginia Vassilevska Williams
  • Yinzhan Xu

We present an almost optimal algorithm for the classic Chamberlin-Courant multiwinner voting rule (CC) on single-peaked preference profiles. Given n voters and m candidates, it runs in almost linear time in the input size improving the previous best O(nm^2) time algorithm. We also study multiwinner voting rules on nearly single-peaked preference profiles in terms of the candidate-deletion operation. We show a polynomial-time algorithm for CC where a given candidate-deletion set D has logarithmic size. Actually, our algorithm runs in 2^|D| * poly(n, m) time and the base of the power cannot be improved under the Strong Exponential Time Hypothesis. We also adapt these results to all non-constant Thiele rules which generalize CC with approval ballots.

PDF Details DOI

MFCS Conference 2022 Conference Paper

New Lower Bounds and Upper Bounds for Listing Avoidable Vertices

  • Mingyang Deng
  • Virginia Vassilevska Williams
  • Ziqian Zhong

We consider the problem of listing all avoidable vertices in a given n vertex graph. A vertex is avoidable if every pair of its neighbors is connected by a path whose internal vertices are not neighbors of the vertex or the vertex itself. Recently, Papadopolous and Zisis showed that one can list all avoidable vertices in O(n^{ω+1}) time, where ω < 2. 373 is the square matrix multiplication exponent, and conjectured that a faster algorithm is not possible. In this paper we show that under the 3-OV Hypothesis, and thus the Strong Exponential Time Hypothesis, n^{3-o(1)} time is needed to list all avoidable vertices, and thus the current best algorithm is conditionally optimal if ω = 2. We then show that if ω > 2, one can obtain an improved algorithm that for the current value of ω runs in O(n^3. 32) time. We also show that our conditional lower bound is actually higher and supercubic, under a natural High Dimensional 3-OV hypothesis, implying that for our current knowledge of rectangular matrix multiplication, the avoidable vertex listing problem likely requires Ω(n^3. 25) time. We obtain further algorithmic improvements for sparse graphs and bounded degree graphs.

Details

SODA Conference 2021 Conference Paper

A Refined Laser Method and Faster Matrix Multiplication

  • Josh Alman
  • Virginia Vassilevska Williams

The complexity of matrix multiplication is measured in terms of ω, the smallest real number such that two n × n matrices can be multiplied using O ( n ω + ∊ ) field operations for all ∊ > 0; the best bound until now is ω < 2. 37287 [Le Gall'14]. All bounds on ω since 1986 have been obtained using the so-called laser method, a way to lower-bound the ‘value’ of a tensor in designing matrix multiplication algorithms. The main result of this paper is a refinement of the laser method that improves the resulting value bound for most sufficiently large tensors. Thus, even before computing any specific values, it is clear that we achieve an improved bound on ω, and we indeed obtain the best bound on ω to date: ω < 2. 37286. The improvement is of the same magnitude as the improvement that [Le Gall'14] obtained over the previous bound [Vassilevska W. '12]. Our improvement to the laser method is quite general, and we believe it will have further applications in arithmetic complexity.

Details

FOCS Conference 2021 Conference Paper

Hardness of Approximate Diameter: Now for Undirected Graphs

  • Mina Dalirrooyfard
  • Ray Li
  • Virginia Vassilevska Williams

Approximating the graph diameter is a basic task of both theoretical and practical interest. A simple folklore algorithm can output a 2-approximation to the diameter in linear time by running BFS from an arbitrary vertex. It has been open whether a better approximation is possible in near-linear time. A series of papers on fine-grained complexity have led to strong hardness results for diameter in directed graphs, culminating in a recent tradeoff curve independently discovered by [Li, STOC'21] and [Dalirrooyfard and Wein, STOC'21], showing that under the Strong Exponential Time Hypothesis (SETH), for any integer $k\geq 2$ and $\delta > 0$, a $2-\frac{1}{k}-\delta$ approximation for diameter in directed $m$ -edge graphs requires $mn^{1+1/(k-1)-o(1)}$ time. In particular, the simple linear time 2-approximation algorithm is optimal for directed graphs. In this paper we prove that the same tradeoff lower bound curve is possible for undirected graphs as well, extending results of [Roditty and Vassilevska W. , STOC'13], [Li'20] and [Bonnet, ICALP'21] who proved the first few cases of the curve, $k=2, 3$ and 4, respectively. Our result shows in particular that the simple linear time 2-approximation algorithm is also optimal for undirected graphs. To obtain our result we develop new tools for fine-grained reductions that could be useful for proving SETH-based hardness for other problems in undirected graphs related to distance computation.

Details

SODA Conference 2021 Conference Paper

New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners

  • Thiago Bergamaschi
  • Monika Henzinger
  • Maximilian Probst Gutenberg
  • Virginia Vassilevska Williams
  • Nicole Wein

Maintaining and updating shortest paths information in a graph is a fundamental problem with many applications. As computations on dense graphs can be prohibitively expensive, and it is preferable to perform the computations on a sparse skeleton of the given graph that roughly preserves the shortest paths information. Spanners and emulators serve this purpose. Unfortunately, very little is known about dynamically maintaining sparse spanners and emulators as the graph is modified by a sequence of edge insertions and deletions. This paper develops fast dynamic algorithms for spanner and emulator maintenance and provides evidence from fine-grained complexity that these algorithms are tight. For unweighted undirected m -edge n -node graphs we obtain the following results. Under the popular OMv conjecture, there can be no decremental or incremental algorithm that maintains an n 1+ o (1) edge (purely additive) + n δ -emulator for any δ < 1/2 with arbitrary polynomial preprocessing time and total update time m 1+ o (1). Also, under the Combinatorial k -Clique hypothesis, any fully dynamic combinatorial algorithm that maintains an n 1+ o (1) edge (1 + ∊, n o (1) )-spanner or emulator for small ∊ must either have preprocessing time mn 1– o (1) or amortized update time m 1– o (1). Both of our conditional lower bounds are tight. As the above fully dynamic lower bound only applies to combinatorial algorithms, we also develop an algebraic spanner algorithm that improves over the m 1– o (1) update time for dense graphs. For any constant ∊ ∊ (0, 1], there is a fully dynamic algorithm with worst-case update time O ( n 1. 529 ) that whp maintains an n 1+ o (1) edge (1 + ∊, n o (1) )-spanner. Our new algebraic techniques allow us to also obtain a new fully dynamic algorithm for All-Pairs Shortest Paths (APSP) that can perform both edge updates and can report shortest paths in worst-case time O ( n 1. 9 ), which are correct whp. This is the first path-reporting fully dynamic APSP algorithm with a truly subquadratic query time that beats O ( n 2. 5 ) update time. It works against an oblivious adversary. Finally, we give two applications of our new dynamic spanner algorithms: (1) a fully dynamic (1 + ∊)-approximate APSP algorithm with update time O ( n 1. 529 ) that can report approximate shortest paths in n 1+ o (1) time per query; previous subquadratic update/query algorithms could only report the distance, but not obtain the paths; (2) a fully dynamic algorithm for near-2-approximate Steiner tree maintenance with both terminal and edge updates.

Details

SODA Conference 2020 Conference Paper

Equivalences between triangle and range query problems

  • Lech Duraj
  • Krzysztof Kleiner
  • Adam Polak 0001
  • Virginia Vassilevska Williams

We define a natural class of range query problems, and prove that all problems within this class have the same time complexity (up to polylogarithmic factors). The equivalence is very general, and even applies to online algorithms. This allows us to obtain new improved algorithms for all of the problems in the class. We then focus on the special case of the problems when the queries are offline and the number of queries is linear. We show that our range query problems are runtime-equivalent (up to polylogarithmic factors) to counting for each edge e in an m -edge graph the number of triangles through e. This natural triangle problem can be solved using the best known triangle counting algorithm, running in ( m 2ω/(ω + 1) < ( m 1. 41 ) time. Moreover, if ω = 2, the ( m 2 ω /( ω + 1) ) running time is known to be tight (within m o (1) factors) under the 3SUM Hypothesis. In this case, our equivalence settles the complexity of the range query problems. Our problems constitute the first equivalence class with this peculiar running time bound. To better understand the complexity of these problems, we also provide a deeper insight into the family of triangle problems, in particular showing black-box reductions between triangle listing and per-edge triangle detection and counting. As a byproduct of our reductions, we obtain a simple triangle listing algorithm matching the state-of-the-art for all regimes of the number of triangles. We also give some not necessarily tight, but still surprising reductions from variants of matrix products, such as the (min, max)-product.

Details

FOCS Conference 2020 Conference Paper

Monochromatic Triangles, Triangle Listing and APSP

  • Virginia Vassilevska Williams
  • Yinzhan Xu

All-Pairs Shortest Paths (APSP) is one of the most basic problems in graph algorithms. Given an n-node directed or undirected graph with integer weights in {-n c, .. ., n c } and no negative cycles, APSP asks to compute the shortest paths distance between every pair of vertices. The fastest known algorithm for APSP runs in n 3 /2 Θ(√{logn}) time [Williams'14], and no truly subcubic time algorithms are known. One of the main hypotheses in fine-grained complexity is that APSP requires n 3-o(1) time. Another famous hypothesis in fine-grained complexity is that the 3SUM problem for n integers (which can be solved in O(n 2 ) time) requires n 2-o(1) time. Although there are no direct reductions between 3SUM and APSP, it is known that they are related: the (min, +)-convolution problem reduces in a fine-grained way to both, and both fine-grained reduce to the Exact Triangle problem. In this paper we find more relationships between these two problems and other basic problems. Pătraşcu had shown that under the 3SUM hypothesis the All-Edges Sparse Triangle problem in m-edge graphs requires m 4/3-o(1) time. The latter problem asks to determine for every edge e, whether e is in a triangle. It is equivalent to the problem of listing m triangles in an m-edge graph where m=-Õ(n 1. 5 ), and can be solved in O(m 1. 41 ) time [Alon et al. '97] with the current matrix multiplication bounds, and in Õ(m 4/3 ) time if ω = 2. We show that one can reduce Exact Triangle to All-Edges Sparse Triangle, showing that All-Edges Sparse Triangle (and hence Triangle Listing) requires m 4/3-o(1) time also assuming the APSP hypothesis. This allows us to provide APSP-hardness for many dynamic problems that were previously known to be hard under the 3SUM hypothesis. We also consider the All-Edges Monochromatic Triangle problem. Via work of [Lincoln et al. '20], our result on All-Edges Sparse Triangle implies that if the All-Edges Monochromatic Triangle problem has an O(n 2. 5-ε ) time algorithm for, then both the APSP and 3SUM hypotheses are false. The fastest algorithm for All-Edges Monochromatic Triangle runs in Õ(n (3+ω)/2 ) time [Vassilevska et al. '06], and our new reduction shows that if ω = 2, this algorithm is best possible, unless 3SUM or APSP can be solved faster. Besides 3SUM, previously the only problems known to be fine-grained reducible to All-Edges Monochromatic Triangle were the seemingly easier problems directed unweighted APSP and Min-Witness Product [Lincoln et al. '20]. Our reduction shows that this problem is much harder. We also connect the problem to other “intermediate” problems, whose runtimes are between O(n ω ) and O(n 3 ), such as the Max-Min product problem.

Details

STOC Conference 2020 Conference Paper

New algorithms and hardness for incremental single-source shortest paths in directed graphs

  • Maximilian Probst Gutenberg
  • Virginia Vassilevska Williams
  • Nicole Wein

In the dynamic Single-Source Shortest Paths (SSSP) problem, we are given a graph G =( V , E ) subject to edge insertions and deletions and a source vertex s ∈ V , and the goal is to maintain the distance d ( s , t ) for all t ∈ V . Fine-grained complexity has provided strong lower bounds for exact partially dynamic SSSP and approximate fully dynamic SSSP [ESA’04, FOCS’14, STOC’15]. Thus much focus has been directed towards finding efficient partially dynamic (1+є)-approximate SSSP algorithms [STOC’14, ICALP’15, SODA’14, FOCS’14, STOC’16, SODA’17, ICALP’17, ICALP’19, STOC’19, SODA’20, SODA’20]. Despite this rich literature, for directed graphs there are no known deterministic algorithms for (1+є)-approximate dynamic SSSP that perform better than the classic ES-tree [JACM’81]. We present the first such algorithm. We present a deterministic data structure for incremental SSSP in weighted directed graphs with total update time Õ( n 2 log W /є O (1) ) which is near-optimal for very dense graphs; here W is the ratio of the largest weight in the graph to the smallest. Our algorithm also improves over the best known partially dynamic randomized algorithm for directed SSSP by Henzinger et al. [STOC’14, ICALP’15] if m =ω( n 1.1 ). Complementing our algorithm, we provide improved conditional lower bounds. Henzinger et al. [STOC’15] showed that under the OMv Hypothesis, the partially dynamic exact s - t Shortest Path problem in undirected graphs requires amortized update or query time m 1/2− o (1) , given polynomial preprocessing time. Under a new hypothesis about finding Cliques, we improve the update and query lower bound for algorithms with polynomial preprocessing time to m 0.626− o (1) . Further, under the k -Cycle hypothesis, we show that any partially dynamic SSSP algorithm with O ( m 2−є ) preprocessing time requires amortized update or query time m 1− o (1) , which is essentially optimal. All previous conditional lower bounds that come close to our bound [ESA’04,FOCS’14] only held for “combinatorial” algorithms, while our new lower bound does not make such restrictions.

Details

FOCS Conference 2020 Conference Paper

New Techniques for Proving Fine-Grained Average-Case Hardness

  • Mina Dalirrooyfard
  • Andrea Lincoln
  • Virginia Vassilevska Williams

The recent emergence of fine-grained cryptography strongly motivates developing an average-case analogue of Fine-Grained Complexity (FGC). Prior work [Goldreich-Rothblum 2018, Boix-Adserà et al. 2019, Ball et al. 2017] developed worst-case to average-case fine-grained reductions (WCtoACFG) for certain algebraic and counting problems over natural distributions and used them to obtain a limited set of cryptographic primitives. To obtain stronger cryptographic primitives based on standard FGC assumptions, ideally, one would like to develop WCtoACFG reductions from the core hard problems of FGC, Orthogonal Vectors (OV), CNF-SAT, 3SUM, All-Pairs Shortest Paths (APSP) and zero- k clique. Unfortunately, it is unclear whether these problems actually are hard for any natural distribution. It is known, that e. g. OV can be solved quickly for very natural distributions [Kane-Williams 2019], and in this paper we show that even counting the number of OV pairs on average has a fast algorithm. This paper defines new versions of OV, kSUM and zero- k-clique that are both worst-case and average-case fine-grained hard assuming the core hypotheses of FGC. We then use these as a basis for fine-grained hardness and average-case hardness of other problems. The new problems represent their inputs in a certain “factored” form. We call them “factored”-OV, “factored”-zero- k-clique and “factored”-3SUM. We show that factored- k-OV and factored kSUM are equivalent and are complete for a class of problems defined over Boolean functions. Factored zero- k-clique is also complete, for a different class of problems. Our hard factored problems are also simple enough that we can reduce them to many other problems, e. g. to edit distance, k-LCS and versions of Max-Flow. We further consider counting variants of the factored problems and give WCtoACFG reductions for them for a natural distribution. Through FGC reductions we then get average-case hardness for well-studied problems like regular expression matching from standard worst-case FGC assumptions. To obtain our WCtoACFG reductions, we formalize the framework of [Boix-Adserà et al. 2019] that was used to give a WCtoACFG reduction for counting k-cliques. We define an explicit property of problems such that if a problem has that property one can use the framework on the problem to get a WCtoACFG self reduction. We then use the framework to slightly extend Bolx-Adserà et al. 's average-case counting k-cliques result to average-case hardness for counting arbitrary subgraph patterns of constant size in -partite graphs. The fine-grained public-key encryption scheme of [LaVigne et al. '20] is based on an average-case hardness hypothesis for the decision problem, zero- k-clique, and the known techniques for building such schemes break down for algebraic/counting problems. Meanwhile, the WCtoACFG reductions so far have only been for counting problems. To bridge this gap, we show that for a natural distribution, an algorithm that detects a zero- k-clique with high enough probability also implies an algorithm that can count zero- k-cliques with high probability. This gives hope that the FGC cryptoscheme of [LaVigne et al. '20] can be based on standard FGC assumptions.

Details

AAMAS Conference 2019 Conference Paper

Bribery in Balanced Knockout Tournaments

  • Christine Konicki
  • Virginia Vassilevska Williams

Balanced knockout tournaments comprise a common format for sporting competitions and pairwise decision-making. In this paper, we investigate the computational complexity of arranging the tournament’s initial seeding and bribing players to guarantee one player’s victory. We give a model of bribery in which the organizer can both arrange the seeding and bribe players to decrease their probability of beating other players at a cost, without exceeding a budget. We also show that it is NP-hard to determine a bribery and a seeding under which a given player wins the tournament with probability 1, even when the pre-bribery matrix is monotonic, and the post-bribery matrix is ϵ-monotonic and very close to the initial one. We also show that for almost all n player inputs generated by a well known deterministic model due to Condorcet, one can always bribe the "top" O(logn) players so that there is an efficiently constructible seeding for which any player wins.

PDF

SODA Conference 2018 Conference Paper

Approximating Cycles in Directed Graphs: Fast Algorithms for Girth and Roundtrip Spanners

  • Jakub Pachocki
  • Liam Roditty
  • Aaron Sidford
  • Roei Tov
  • Virginia Vassilevska Williams

The girth of a graph, i. e. the length of its shortest cycle, is a fundamental graph parameter. Unfortunately all known algorithms for computing, even approximately, the girth and girth-related structures in directed weighted m -edge and n -node graphs require Ω(min{ n ω, mn }) time (for 2 ≤ ω < 2. 373). In this paper, we drastically improve these runtimes as follows: • Multiplicative Approximations in Nearly Linear Time: We give an algorithm that in Õ ( m ) time computes an Õ (1)-multiplicative approximation of the girth as well as an Õ (1)-multiplicative roundtrip spanner with Õ ( n ) edges with high probability (w. h. p). • Nearly Tight Additive Approximations: For unweighted graphs and any a ∊ (0, 1) we give an algorithm that in Õ ( mn 1– a ) time computes an O ( n a )-additive approximation of the girth, w. h. p. We show that the runtime of our algorithm cannot be significantly improved without a breakthrough in combinatorial boolean matrix multiplication. We also show that if the girth is O ( n a ), then the same guarantee can be achieved via a deterministic algorithm. Our main technical contribution to achieve these results is the first nearly linear time algorithm for computing roundtrip covers, a directed graph decomposition concept key to previous roundtrip spanner constructions. Previously it was not known how to compute these significantly faster than Ω( mn ) time. Given the traditional difficulty in efficiently processing directed graphs, we hope our techniques may find further applications.

Details

FOCS Conference 2018 Conference Paper

Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication

  • Josh Alman
  • Virginia Vassilevska Williams

We study the known techniques for designing Matrix Multiplication algorithms. The two main approaches are the Laser method of Strassen, and the Group theoretic approach of Cohn and Umans. We define a generalization based on zeroing outs which subsumes these two approaches, which we call the Solar method, and an even more general method based on monomial degenerations, which we call the Galactic method. We then design a suite of techniques for proving lower bounds on the value of omega, the exponent of matrix multiplication, which can be achieved by algorithms using many tensors T and the Galactic method. Some of our techniques exploit 'local' properties of T, like finding a sub-tensor of T which is so 'weak' that T itself couldn't be used to achieve a good bound on omega, while others exploit 'global' properties, like T being a monomial degeneration of the structural tensor of a group algebra. Our main result is that there is a universal constant ℓ>2 such that a large class of tensors generalizing the Coppersmith-Winograd tensor CW_q cannot be used within the Galactic method to show a bound on omega better than ell, for any q. We give evidence that previous lower-bounding techniques were not strong enough to show this. We also prove a number of complementary results along the way, including that for any group G, the structural tensor of C[G] can be used to recover the best bound on omega which the Coppersmith-Winograd approach gets using CW_|G|-2 as long as the asymptotic rank of the structural tensor is not too large.

Details

SODA Conference 2018 Conference Paper

Optimal Vertex Fault Tolerant Spanners (for fixed stretch)

  • Greg Bodwin
  • Michael Dinitz
  • Merav Parter
  • Virginia Vassilevska Williams

A k-spanner of a graph G is a sparse subgraph H whose shortest path distances match those of G up to a multiplicative error k. In this paper we study spanners that are resistant to faults. A subgraph H ⊆ G is an f vertex fault tolerant ( VFT ) k -spanner if H \ F is a k -spanner of G \ F for any small set F of f vertices that might “fail. ” One of the main questions in the area is: what is the minimum size of an f fault tolerant k -spanner that holds for all n node graphs (as a function of f, k and n )? This question was first studied in the context of geometric graphs [Levcopoulos et al. STOC ’98, Czumaj and Zhao SoCG ’03] and has more recently been considered in general undirected graphs [Chechik et al. STOC ’09, Dinitz and Krauthgamer PODC ’11]. In this paper, we settle the question of the optimal size of a VFT spanner, in the setting where the stretch factor k is fixed. Specifically, we prove that every (undirected, possibly weighted) n -node graph G has a (2 k – 1)- spanner resilient to f vertex faults with O k ( f 1–1/k n 1+1/ k ) edges, and this is fully optimal (unless the famous Erdös Girth Conjecture is false). Our lower bound even generalizes to imply that no data structure capable of approximating dist G\F ( s, t ) similarly can beat the space usage of our spanner in the worst case. To the best of our knowledge, this is the first instance in fault tolerant network design in which introducing fault tolerance to the structure increases the size of the (non-FT) structure by a sublinear factor in f. Another advantage of this result is that our spanners are constructed by a very natural and simple greedy algorithm, which is the obvious extension of the standard greedy algorithm used to build spanners in the non-faulty setting. We also consider the edge fault tolerant (EFT) model, defined analogously with edge failures rather than vertex failures. We show that the same spanner upper bound applies in this setting. Our data structure lower bound extends to the case k = 2 (and hence we close the EFT problem for 3-approximations), but it falls to D( f 1/2-1/(2 k ) · n 1+1/ k ) for k > 3. We leave it as an open problem to close this gap.

Details

STOC Conference 2018 Conference Paper

Towards tight approximation bounds for graph diameter and eccentricities

  • Arturs Backurs
  • Liam Roditty
  • Gilad Segal
  • Virginia Vassilevska Williams
  • Nicole Wein

Among the most important graph parameters is the Diameter, the largest distance between any two vertices. There are no known very efficient algorithms for computing the Diameter exactly. Thus, much research has been devoted to how fast this parameter can be approximated . Chechik et al. [SODA 2014] showed that the diameter can be approximated within a multiplicative factor of 3/2 in Õ( m 3/2 ) time. Furthermore, Roditty and Vassilevska W. [STOC 13] showed that unless the Strong Exponential Time Hypothesis (SETH) fails, no O ( n 2−ε ) time algorithm can achieve an approximation factor better than 3/2 in sparse graphs. Thus the above algorithm is essentially optimal for sparse graphs for approximation factors less than 3/2. It was, however, completely plausible that a 3/2-approximation is possible in linear time. In this work we conditionally rule out such a possibility by showing that unless SETH fails no O ( m 3/2−ε ) time algorithm can achieve an approximation factor better than 5/3. Another fundamental set of graph parameters are the Eccentricities. The Eccentricity of a vertex v is the distance between v and the farthest vertex from v . Chechik et al. [SODA 2014] showed that the Eccentricities of all vertices can be approximated within a factor of 5/3 in Õ( m 3/2 ) time and Abboud et al. [SODA 2016] showed that no O ( n 2−ε ) algorithm can achieve better than 5/3 approximation in sparse graphs. We show that the runtime of the 5/3 approximation algorithm is also optimal by proving that under SETH, there is no O ( m 3/2−ε ) algorithm that achieves a better than 9/5 approximation. We also show that no near-linear time algorithm can achieve a better than 2 approximation for the Eccentricities. This is the first lower bound in fine-grained complexity that addresses near-linear time computation. We show that our lower bound for near-linear time algorithms is essentially tight by giving an algorithm that approximates Eccentricities within a 2+δ factor in Õ( m /δ) time for any 0<δ<1. This beats all Eccentricity algorithms in Cairo et al. [SODA 2016] and is the first constant factor approximation for Eccentricities in directed graphs. To establish the above lower bounds we study the S - T Diameter problem: Given a graph and two subsets S and T of vertices, output the largest distance between a vertex in S and a vertex in T . We give new algorithms and show tight lower bounds that serve as a starting point for all other hardness results. Our lower bounds apply only to sparse graphs. We show that for dense graphs, there are near-linear time algorithms for S - T Diameter, Diameter and Eccentricities, with almost the same approximation guarantees as their Õ( m 3/2 ) counterparts, improving upon the best known algorithms for dense graphs.

Details

AAMAS Conference 2017 Conference Paper

Parameterized Complexity of Group Activity Selection

  • Hooyeon Lee
  • Virginia Vassilevska Williams

We consider the Group Activity Selection Problem (GASP) in which a group of agents need to be assigned to activities, subject to agent preferences and stability conditions. In GASP, the agents announce dichotomic preferences on which (activity, number-of-participant) pairs are acceptable to them. We consider five solution concepts of assignments: (1) individual rationality (everyone who is assigned to an activity is willing to participate), (2) (Nash) stability (no agent wants to deviate from the assignment), (3) envy-freeness (no agent is envious of someone else’s assignment), (4) stability and envyfreeness, and (5) perfection (everyone is assigned and willing to participate). It is known that finding an assignment of a given size with any of these properties is NP-complete. We study the complexity of GASPon a finer scale, through the lens of parameterized complexity. We show that the solution concepts above differ substantially, when parameterized by the size of the solution (the number of assigned agents or the number of used activities). In particular, finding an individually rational assignment is fixed parameter tractable, yet other solutions concepts are less tractable (W[1]- and W[2]-hard) even under very natural restrictions on inputs.

PDF

SODA Conference 2016 Conference Paper

Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs

  • Amir Abboud
  • Virginia Vassilevska Williams
  • Joshua R. Wang

The radius and diameter are fundamental graph parameters, with several natural definitions for directed graphs. Each definition is well-motivated in a variety of applications. All versions of diameter and radius can be solved via solving all-pairs shortest paths (APSP), followed by a fast postprocessing step. However, solving APSP on n -node graphs requires Ω( n 2 ) time even in sparse graphs. We study the question: when can diameter and radius in sparse graphs be solved in truly subquadratic time, and when is such an algorithm unlikely? Motivated by our conditional lower bounds on computing these measures exactly in truly subquadratic time, we search for approximation and fixed parameter subquadratic algorithms, and alternatively, for reasons why they do not exist. We find that: Most versions of Diameter and Radius can be solved in truly subquadratic time with optimal approximation guarantees, under plausible assumptions. For example, there is a 2-approximation algorithm for directed Radius with one-way distances that runs in time, while a (2 – δ )-approximation algorithm in O ( n 2– ∊ ) time is considered unlikely. On graphs with treewidth k, we can solve all versions in 2 O ( k log k ) n 1+ O (1) time. We show that these algorithms are near optimal since even a (3/2 – δ )-approximation algorithm that runs in time 2 o (k) n 2– ∊ would refute plausible assumptions. Two conceptual contributions of this work that we hope will incite future work are: the introduction of a Fixed Parameter Tractability in P framework, and the statement of a differently-quantified variant of the Orthogonal Vectors Conjecture, which we call the Hitting Set Conjecture.

Details

SODA Conference 2016 Conference Paper

Better Distance Preservers and Additive Spanners

  • Greg Bodwin
  • Virginia Vassilevska Williams

We make improvements to the upper bounds on several popular types of distance preserving graph sketches. The first part of our paper concerns pairwise distance preservers, which are sparse subgraphs that exactly preserve the pairwise distances for a set of given pairs of vertices. Our main result here is that all unweighted, undirected n -node graphs G and all pair sets P have distance preservers on | H | = O ( n 2 / 3 | P | 2 / 3 + n | P | 1 / 3 ) edges. This improves the known bounds whenever | P | = ω ( n 3/4 ). We then develop a new graph clustering technique, based on distance preservers, and we apply this technique to show new upper bounds for additive ( standard ) spanners, in which all pairwise distances must be preserved up to an additive error function, and for subset spanners, in which only distances within a given node subset must be preserved up to an error function. For both of these objects, we obtain the new best tradeoff between spanner sparsity and error allowance in the regime where the error is polynomial in the graph size. We leave open a conjecture that O ( n 2/3 | P | 2/3 + n ) pairwise distance preservers are possible for undirected unweighted graphs. Resolving this conjecture in the affirmative would improve and simplify our upper bounds for all the graph sketches mentioned above.

Details

MFCS Conference 2016 Invited Paper

RNA-Folding - From Hardness to Algorithms

  • Virginia Vassilevska Williams

This is an overview of the invited talk delivered at the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS-2016).

Details

STOC Conference 2016 Conference Paper

Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made

  • Amir Abboud
  • Thomas Dueholm Hansen
  • Virginia Vassilevska Williams
  • R. Ryan Williams

A recent, 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 computing the Edit Distance of two sequences of length n in truly subquadratic O ( n 2−ε ) time, for some ε>0, is impossible 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 more expressive representations, like subexponential-size NC circuits. Intuitively, this assumption is much more plausible: NC circuits can implement linear algebra and 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 far more remarkable consequences 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−ε) n time. An interesting feature of our work is that we get major consequences even from mildly subquadratic algorithms for Edit Distance or LCS. For example, we show that if an arbitrarily large polylog factor is shaved from n 2 for Edit Distance then NEXP does not have non-uniform NC 1 circuits.

Details

FOCS Conference 2016 Conference Paper

Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product

  • Karl Bringmann
  • Fabrizio Grandoni 0001
  • Barna Saha
  • Virginia Vassilevska Williams

It is a major open problem whether the (min, +)-product of two n by n matrices has a truly sub-cubic time algorithm, as it is equivalent to the famous All-Pairs-Shortest-Paths problem (APSP) in n-vertex graphs. There are some restrictions of the (min, +)-product to special types of matrices that admit truly sub-cubic algorithms, each giving rise to a special case of APSP that can be solved faster. In this paper we consider a new, different and powerful restriction in which one matrix can be arbitrary, as long as the other matrix has "bounded differences" in either its columns or rows, i. e. any two consecutive entries differ by only a small amount. We obtain the first truly sub-cubic algorithm for this Bounded Differences (min, +)-product (answering an open problem of Chan and Lewenstein). Our new algorithm, combined with a strengthening of an approach of L. Valiant for solving context-free grammar parsing with matrix multiplication, yields the first truly sub-cubic algorithms for the following problems: Language Edit Distance (a major problem in the parsing community), RNA-folding (a major problem in bioinformatics) and Optimum Stack Generation (answering an open problem of Tarjan).

Details

SODA Conference 2015 Conference Paper

Finding Four-Node Subgraphs in Triangle Time

  • Virginia Vassilevska Williams
  • Joshua R. Wang
  • R. Ryan Williams
  • Huacheng Yu

We present new algorithms for finding induced four-node subgraphs in a given graph, which run in time roughly that of detecting a clique on three nodes (i. e. , a triangle). The best known algorithms for triangle finding in an n -node graph take O ( n ω ) time, where ω < 2. 373 is the matrix multiplication exponent. We give a general randomized technique for finding any induced four-node subgraph, except for the clique or independent set on 4 nodes, in Õ ( n ω ) time with high probability. The algorithm can be derandomized in some cases: we show how to detect a diamond (or its complement) in deterministic Õ ( n ω ) time. Our approach substantially improves on prior work. For instance, the previous best algorithm for C 4 detection ran in O ( n 3. 3 ) time, and for diamond detection in O ( n 3 ) time. For sparse graphs with m edges, the best known triangle finding algorithm runs in O ( m 2 ω / ( ω +1) ) ≤ O ( m 1. 41 ) time. We give a randomized Õ ( m 2 ω /( ω +1) ) time algorithm (analogous to the best known for triangle finding) for finding any induced four-node subgraph other than C 4, K 4 and their complements. In the case of diamond detection, we also design a deterministic Õ ( m 2 ω /( ω +1) ) time algorithm. For C 4 or its complement, we give randomized Õ ( m (4 ω– 1)/(2 ω +1) ) ≤ O ( m 1. 48 ) time finding algorithms. These algorithms substantially improve on prior work. For instance, the best algorithm for diamond detection ran in O ( m 1. 5 ) time.

Details

IJCAI Conference 2015 Conference Paper

Fixing Tournaments for Kings, Chokers, and More

  • Michael P. Kim
  • Virginia Vassilevska Williams

We study the tournament fixing problem (TFP), which asks whether a tournament organizer can rig a single-elimination (SE) tournament such that their favorite player wins, simply by adjusting the initial seeding. Prior results give two perspectives of TFP: on the one hand, deciding whether an arbitrary player can win any SE tournament is known to be NP-complete; on the other hand, there are a number of known conditions, under which a player is guaranteed to win some SE tournament. We extend and connect both these lines of work. We show that for a number of structured variants of the problem, where our player is seemingly strong, deciding whether the player can win any tournament is still NP-complete. Dual to this hardness result, we characterize a new set of sufficient conditions for a player to win a tournament. Further, we give an improved exact algorithm for deciding whether a player can win a tournament.

PDF Details

FOCS Conference 2015 Conference Paper

If the Current Clique Algorithms are Optimal, So is Valiant's Parser

  • Amir Abboud
  • Arturs Backurs
  • Virginia Vassilevska Williams

The CFG recognition problem is: given a context-free grammar G and a string w of length n, decide if w can be obtained from 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(nO) time, where? <; 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(n3= log3 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(|G| n3 -- e) can be converted into a surprising subcubic algorithm for Boolean Matrix Multiplication. Unfortunately, Lee' s hardness result required that the grammar size be |G| = O(n6). 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).

Details

STOC Conference 2015 Conference Paper

Matching Triangles and Basing Hardness on an Extremely Popular Conjecture

  • Amir Abboud
  • Virginia Vassilevska Williams
  • Huacheng Yu

Due to the lack of unconditional polynomial lower bounds, it is now in fashion to prove conditional lower bounds in order to advance our understanding of the class P. The vast majority of these lower bounds are based on one of three famous hypotheses: the 3-SUM conjecture, the APSP conjecture, and the Strong Exponential Time Hypothesis. Only circumstantial evidence is known in support of these hypotheses, and no formal relationship between them is known. In hopes of obtaining "less conditional" and therefore more reliable lower bounds, we consider the conjecture that at least one of the above three hypotheses is true. We design novel reductions from 3-SUM, APSP, and CNF-SAT, and derive interesting consequences of this very plausible conjecture, including: Tight n 3-o(1) lower bounds for purely-combinatorial problems about the triangles in unweighted graphs. New n 1-o(1) lower bounds for the amortized update and query times of dynamic algorithms for single-source reachability, strongly connected components, and Max-Flow. New n 1.5-o(1) lower bound for computing a set of n st-maximum-flow values in a directed graph with n nodes and ~O(n) edges. There is a hierarchy of natural graph problems on n nodes with complexity n c for c ∈ (2,3). Only slightly non-trivial consequences of this conjecture were known prior to our work. Along the way we also obtain new conditional lower bounds for the Single-Source-Max-Flow problem.

Details

SODA Conference 2015 Conference Paper

Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter

  • Amir Abboud
  • Fabrizio Grandoni 0001
  • Virginia Vassilevska Williams

Measuring the importance of a node in a network is a major goal in the analysis of social networks, biological systems, transportation networks etc. Different centrality measures have been proposed to capture the notion of node importance. For example, the center of a graph is a node that minimizes the maximum distance to any other node (the latter distance is the radius of the graph). The median of a graph is a node that minimizes the sum of the distances to all other nodes. Informally, the betweenness centrality of a node w measures the fraction of shortest paths that have w as an intermediate node. Finally, the reach centrality of a node w is the smallest distance r such that any s - t shortest path passing through w has either s or t in the ball of radius r around w. The fastest known algorithms to compute the center and the median of a graph, and to compute the betweenness or reach centrality even of a single node take roughly cubic time in the number n of nodes in the input graph. It is open whether these problems admit truly subcubic algorithms, i. e. algorithms with running time Õ ( n 3– δ ) for some constant δ > 0 1. We relate the complexity of the mentioned centrality problems to two classical problems for which no truly subcubic algorithm is known, namely All Pairs Shortest Paths (APSP) and Diameter. We show that Radius, Median and Betweenness Centrality are equivalent under subcubic reductions to APSP, i. e. that a truly subcubic algorithm for any of these problems implies a truly subcubic algorithm for all of them. We then show that Reach Centrality is equivalent to Diameter under subcubic reductions. The same holds for the problem of approximating Betweenness Centrality within any constant factor. Thus the latter two centrality problems could potentially be solved in truly subcubic time, even if APSP requires essentially cubic time.

Details

FOCS Conference 2015 Conference Paper

Tight Hardness Results for LCS and Other Sequence Similarity Measures

  • Amir Abboud
  • Arturs Backurs
  • Virginia Vassilevska Williams

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 for any constant ε >0, an O(n 2-ε ) time algorithm 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).

Details

SODA Conference 2014 Conference Paper

Better Approximation Algorithms for the Graph Diameter

  • Shiri Chechik
  • Daniel H. Larkin
  • Liam Roditty
  • Grant Schoenebeck
  • Robert Endre Tarjan
  • Virginia Vassilevska Williams

The diameter is a fundamental graph parameter and its computation is necessary in many applications. The fastest known way to compute the diameter exactly is to solve the All-Pairs Shortest Paths (APSP) problem. In the absence of fast algorithms, attempts were made to seek fast algorithms that approximate the diameter. In a seminal result Aingworth, Chekuri, Indyk and Motwani [SODA'96 and SICOMP'99] designed an algorithm that computes in time an estimate for the diameter D in directed graphs with nonnegative edge weights, such that ⌊⅔ · D ⌋ – ( M – 1) ≤ ≤ D, where M is the maximum edge weight in the graph. In recent work, Roditty and Vassilevska W. [STOC 13] gave a Las Vegas algorithm that has the same approximation guarantee but improves the (expected) runtime to. Roditty and Vassilevska W. also showed that unless the Strong Exponential Time Hypothesis fails, no ( n 2− ∊ ) time algorithm for sparse unweighted undirected graphs can achieve an approximation ratio better than. Thus their algorithm is essentially tight for sparse unweighted graphs. For weighted graphs however, the approximation guarantee can be meaningless, as M can be arbitrarily large. In this paper we exhibit two algorithms that achieve a genuine -approximation for the diameter, one running in time, and one running in time. Furthermore, our algorithms are deterministic, and thus we present the first deterministic (2 – ∊ )-approximation algorithm for the diameter that takes subquadratic time in sparse graphs. In addition, we address the question of obtaining an additive c -approximation for the diameter, i. e. an estimate such that D – c ≤ ≤ D. An extremely simple time algorithm achieves an additive n ∊ -approximation; no better results are known. We show that for any ∊ > 0, getting an additive n ∊ -approximation algorithm for the diameter running in ( n 2− δ ) time for any δ > 2 ∊ would falsify the Strong Exponential Time Hypothesis. Thus the simple algorithm is probably essentially tight for sparse graphs, and moreover, obtaining a subquadratic time additive c -approximation for any constant c is unlikely. Finally, we consider the problem of computing the eccentricities of all vertices in an undirected graph, i. e. the largest distance from each vertex. Roditty and Vassilevska W. [STOC 13] show that in time, one can compute for each v ∊ V in an undirected graph, an estimate ∊( v ) for the eccentricity ∊( v ) such that max { R, · ∊( v )} ≤ ∊( v ) ≤ min { D, · ∊( v )} where R = min v ∊(v) is the radius of the graph. Here we improve the approximation guarantee by showing that a variant of the same algorithm can achieve estimates ∊ ′ ( v ) with · ∊( v ) ≤ ∊′ ( v ) ≤ ∊( v ).

Details

FOCS Conference 2014 Conference Paper

Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems

  • Amir Abboud
  • Virginia Vassilevska Williams

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-ε ) time for some ε > 0? 2) Can one determine the satisfiability of a CNF formula on n variables and poly n clauses in O(( 2 - ε )npoly n) time for some ε > 0? 3) Is the All Pairs Shortest Paths problem for graphs on n vertices in O(n 3-ε ) time for some ε > 0? 4) Is there a linear time algorithm that detects whether a given graph contains a triangle? 5) Is there an O(n 3-ε ) time combinatorial algorithm for n×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].

Details

STOC Conference 2013 Conference Paper

Fast approximation algorithms for the diameter and radius of sparse graphs

  • Liam Roditty
  • Virginia Vassilevska Williams

The diameter and the radius of a graph are fundamental topological parameters that have many important practical applications in real world networks. The fastest combinatorial algorithm for both parameters works by solving the all-pairs shortest paths problem (APSP) and has a running time of ~O(mn) in m-edge, n-node graphs. In a seminal paper, Aingworth, Chekuri, Indyk and Motwani [SODA'96 and SICOMP'99] presented an algorithm that computes in ~O(m√ n + n 2 ) time an estimate D for the diameter D, such that ⌊ 2/3 D ⌋ ≤ ^D ≤ D. Their paper spawned a long line of research on approximate APSP. For the specific problem of diameter approximation, however, no improvement has been achieved in over 15 years. Our paper presents the first improvement over the diameter approximation algorithm of Aingworth et. al, producing an algorithm with the same estimate but with an expected running time of ~O(m√ n). We thus show that for all sparse enough graphs, the diameter can be 3/2-approximated in o(n 2 ) time. Our algorithm is obtained using a surprisingly simple method of neighborhood depth estimation that is strong enough to also approximate, in the same running time, the radius and more generally, all of the eccentricities, i.e. for every node the distance to its furthest node. We also provide strong evidence that our diameter approximation result may be hard to improve. We show that if for some constant ε>0 there is an O(m 2-ε ) time (3/2-ε)-approximation algorithm for the diameter of undirected unweighted graphs, then there is an O*( (2-δ) n ) time algorithm for CNF-SAT on n variables for constant δ>0, and the strong exponential time hypothesis of [Impagliazzo, Paturi, Zane JCSS'01] is false. Motivated by this negative result, we give several improved diameter approximation algorithms for special cases. We show for instance that for unweighted graphs of constant diameter D not divisible by 3, there is an O(m 2-ε ) time algorithm that gives a (3/2-ε) approximation for constant ε>0. This is interesting since the diameter approximation problem is hardest to solve for small D.

Details

FOCS Conference 2012 Conference Paper

Improved Distance Sensitivity Oracles via Fast Single-Source Replacement Paths

  • Fabrizio Grandoni 0001
  • Virginia Vassilevska Williams

A distance sensitivity oracle is a data structure which, given two nodes s and t in a directed edge-weighted graph G and an edge e, returns the shortest length of an s-t path not containing e, a so called replacement path for the triple (s, t, e). Such oracles are used to quickly recover from edge failures. In this paper we consider the case of integer weights in the interval [-M, M], and present the first distance sensitivity oracle that achieves simultaneously subcubic preprocessing time and sublinear query time. More precisely, for a given parameter α ∈ [0, 1], our oracle has preprocessing time Õ(Mn ω+1/2 +Mn ω+α(4-ω) ) and query time Õ(n 1-α ). Here w ω+1-α ) preprocessing time and (superlinear) Õ(n 1+α ) query time [Weimann, Yuster-FOCS'10]. The main novelty in our approach is an algorithm to compute all the replacement paths from a given source s, an interesting problem on its own. We can solve the latter single-source replacement paths problem in Õ(APSP(n, M))) time, where APSP(n, M) 0. 681 n 2. 575 ) [Zwick-JACM'02] is the runtime for computing all-pairs shortest paths in a graph with n vertices and integer edge weights in [-M, M]. For positive weights the runtime of our algorithm reduces to Õ(Mn ω ). This matches the best known runtime for the simpler replacement paths problem in which both the source s and the target t are fixed [Vassilevska-SODA'11].

Details

STOC Conference 2012 Conference Paper

Multiplying matrices faster than coppersmith-winograd

  • Virginia Vassilevska Williams

We develop an automated approach for designing matrix multiplication algorithms based on constructions similar to the Coppersmith-Winograd construction. Using this approach we obtain a new improved bound on the matrix multiplication exponent ω<2.3727.

Details

SODA Conference 2011 Conference Paper

Faster Replacement Paths

  • Virginia Vassilevska Williams

The replacement paths problem for directed graphs is to find for given nodes s and t and every edge e on the shortest path between them, the shortest path between s and t which avoids e. For unweighted directed graphs on n vertices, the best known algorithm runtime was OT ( n 2. 5 ) by Roditty and Zwick. For graphs with integer weights in {– M, …, M }, Weimann and Yuster showed that one can use fast matrix multiplication and solve the problem in O ( Mn 2, 584 ) time, a runtime which would be O ( Mn 2, 33 ) if the exponent ω of matrix multiplication is 2. We improve on both of these algorithms. Our new algorithm also relies on fast matrix multiplication and runs in Mn ω+ o (1 ) time. Our result shows that, at least for small integer weights, the replacement paths problem in directed graphs may be easier than the related all pairs shortest paths problem in directed graphs, as the current best runtime for the latter is Ω( n 2, 5 ) time even if ω = 2.

Details

FOCS Conference 2011 Conference Paper

Minimum Weight Cycles and Triangles: Equivalences and Algorithms

  • Liam Roditty
  • Virginia Vassilevska Williams

We consider the fundamental algorithmic problem of finding a cycle of minimum weight in a weighted graph. In particular, we show that the minimum weight cycle problem in an undirected n-node graph with edge weights in {1, .. ., M} or in a directed n-node graph with edge weights in {-M, .. ., M} and no negative cycles can be efficiently reduced to finding a minimum weight triangle in an Θ(n)- node undirected graph with weights in {1, .. ., O(M)}. Roughly speaking, our reductions imply the following surprising phenomenon: a minimum cycle with an arbitrary number of weighted edges can be "encoded" using only three edges within roughly the same weight interval! This resolves a longstanding open problem posed in a seminal work by Itai and Rodeh [SIAM J. Computing 1978] on minimum cycle in unweighted graphs. A direct consequence of our efficient reductions are Õ(Mn ω ) ≤ 6(Mn 2. 376 )-time algorithms using fast matrix multiplication (FMM) for finding a minimum weight cycle in both undirected graphs with integral weights from the interval [1, M] and directed graphs with integral weights from the interval [-M, M]. The latter seems to reveal a strong separation between the all pairs shortest paths (APSP) problem and the minimum weight cycle problem in directed graphs as the fastest known APSP algorithm has a running time of O(M 0. 681 n 2. 575 ) by Zwick [J. ACM 2002]. In contrast, when only combinatorial algorithms are allowed (that is, without FMM) the only known solution to minimum weight cycle is by computing APSP. Interestingly, any separation between the two problems in this case would be an amazing breakthrough as by a recent paper by Vassilevska W. and Williams [FOCS'10], any O(n3 -ε )-time algorithm (ε >; 0) for minimum weight cycle immediately implies a O(n 3-δ )-time algorithm (δ >; 0) for APSP.

Details

IJCAI Conference 2011 Conference Paper

Rigging Tournament Brackets for Weaker Players

  • Isabelle Stanton
  • Virginia Vassilevska Williams

Consider the following problem in game manipulation. A tournament designer who has full knowledge of the match outcomes between any possible pair of players would like to create a bracket for a balanced single-elimination tournament so that their favorite player will win. Although this problem has been studied in the areas of voting and tournament manipulation, it is still unknown whether it can be solved in polynomial time. We focus on identifying several general cases for which the tournament can always be rigged efficiently so that the given player wins. We give constructive proofs that, under some natural assumptions, if a player is ranked among the top K players, then one can efficiently rig the tournament for thegiven player, even when K is as large as 19% of the players.

PDF Details DOI

FOCS Conference 2010 Conference Paper

Subcubic Equivalences between Path, Matrix and Triangle Problems

  • Virginia Vassilevska Williams
  • R. Ryan Williams

We say an algorithm on n × n matrices with entries in [-M, M] (or n-node graphs with edge weights from [-M, M]) is truly subcubic if it runs in O(n 3-δ - poly(log M)) time for some δ > 0. We define a notion of subcubic reducibility, and show that many important problems on graphs and matrices solvable in O(n 3 ) time are equivalent under subcubic reductions. Namely, the following weighted problems either all have truly subcubic algorithms, or none of them do: The all-pairs shortest paths problem (APSP). Detecting if a weighted graph has a triangle of negative total edge weight. Listing up to n 2. 99 negative triangles in an edge-weighted graph. Finding a minimum weight cycle in a graph of nonnegative edge weights. The replacement paths problem in an edge-weighted digraph. Finding the second shortest simple path between two nodes in an edge-weighted digraph. Checking whether a given matrix defines a metric. Verifying the correctness of a matrix product over the (min, +)-semiring. Therefore, if APSP cannot be solved in n3-ε time for any ε > 0, then many other problems also need essentially cubic time. In fact we show generic equivalences between matrix products over a large class of algebraic structures used in optimization, verifying a matrix product over the same structure, and corresponding triangle detection problems over the structure. These equivalences simplify prior work on subcubic algorithms for all-pairs path problems, since it now suffices to give appropriate subcubic triangle detection algorithms. Other consequences of our work are new combinatorial approaches to Boolean matrix multiplication over the (OR, AND)semiring (abbreviated as BMM). We show that practical advances in triangle detection would imply practical BMM algorithms, among other results. Building on our techniques, we give two new BMM algorithms: a derandomization of the recent combinatorial BMM algorithm of Bansal and Williams (FOCS'09), and an improved quantum algorithm for BMM.

Details

STOC Conference 2009 Conference Paper

Finding, minimizing, and counting weighted subgraphs

  • Virginia Vassilevska Williams
  • R. Ryan Williams

For a pattern graph H on k nodes, we consider the problems of finding and counting the number of (not necessarily induced) copies of H in a given large graph G on n nodes, as well as finding minimum weight copies in both node-weighted and edge-weighted graphs. Our results include: The number of copies of an H with an independent set of size s can be computed exactly in O*(2 s n k-s+3 ) time. A minimum weight copy of such an H (with arbitrary real weights on nodes and edges) can be found in O(4 s+o(s) n k-s+3 ) time. (The O* notation omits (k) factors.) These algorithms rely on fast algorithms for computing the permanent of a k x n matrix, over rings and semirings. The number of copies of any H having minimum (or maximum) node-weight (with arbitrary real weights on nodes) can be found in O(n ω k/3 + n 2k/3+o(1) ) time, where ω 0, unless the 3SUM problem on N numbers can be solved in O(N 2 - ε ) time. This suggests that the edge-weighted problem is much harder than its node-weighted version.

Details

STOC Conference 2007 Conference Paper

All-pairs bottleneck paths for general graphs in truly sub-cubic time

  • Virginia Vassilevska Williams
  • R. Ryan Williams
  • Raphael Yuster

In the all-pairs bottleneck paths (APBP) problem (a.k.a. all-pairs maximum capacity paths), one is given a directed graph with real non-negative capacities on its edges and is asked to determine, for all pairs of vertices s and t, the capacity of a single path for which a maximum amount of flow can be routed from s to t. The APBP problem was first studied in operations research, shortly after the introduction of maximum flows and all-pairs shortest paths. We present the first truly sub-cubic algorithm for APBP in general dense graphs. In particular, we give a procedure for computing the (max, min)-product of two arbitrary matrices over R ∪ (∞,-∞) in O(n 2+Ω/3 ) ≤ O(n 2.792 ) time, where n is the number of vertices and Ω is the exponent for matrix multiplication over rings. Using this procedure, an explicit maximum bottleneck path for any pair of nodes can be extracted in time linear in the length of the path.

Details

STOC Conference 2006 Conference Paper

Finding a maximum weight triangle in n 3-Delta time, with applications

  • Virginia Vassilevska Williams
  • R. Ryan Williams

We present the first truly sub-cubic algorithms for finding a maximum node-weighted triangle in directed and undirected graphs with arbitrary real weights. The first is an O(B • n 3+ω/2 ) = O(B • n 2.688 ) deterministic algorithm, where n is the number of nodes, ω is the matrix multiplication exponent, and B is the number of bits of precision. The second is a strongly polynomial randomized algorithm that runs in O(n 3+ω/2 log n) expected worst-case time. To achieve this, we show how to efficiently sample a weighted triangle uniformly at random, out of just those triangles whose total weight falls in some prescribed interval (W 1 ,W 2 ) for arbitrary weights W 1 and W 2 . Previous approaches to the problem resulted in time bounds with either an exponential dependence on B, or a runtime of the form Ω(n 3 /(log n) c ). The algorithms are easily extended to finding a maximum node-weighted induced subgraph on 3k nodes in Õ(n (3+ω) k/2) = O(n 2.688 k ) time.We give applications to a variety of problems, including a stable matching problem between buyers and sellers in computational economics, and discuss the possibility of extending our approach to a truly sub-cubic algorithm for computing all-pairs shortest paths on directed graphs with arbitrary weights.

Details

MFCS Conference 2005 Conference Paper

Explicit Inapproximability Bounds for the Shortest Superstring Problem

  • Virginia Vassilevska Williams

Abstract Given a set of strings S = { s 1, .. ., s n }, the Shortest Superstring problem asks for the shortest string s which contains each s i as a substring. We consider two measures of success in this problem: the length measure, which is the length of s, and the compression measure, which is the difference between the sum of lengths of the s i and the length of s. Both the length and the compression versions of the problem are known to be MAX-SNP-hard. The only explicit approximation ratio lower bounds are by Ott: 1. 000057 for the length measure and 1. 000089 for the compression measure. Using a natural construction we improve these lower bounds to 1. 00082 for the length measure and 1. 00093 for the compression measure. Our lower bounds hold even for instances in which the strings are over a binary alphabet and have equal lengths. In fact, we show a somewhat surprising result, that the Shortest Superstring problem (with respect to both measures) is as hard to approximate on instances over a binary alphabet, as it is over any alphabet.

Details
v2026.09.13