49 citations · 193 across the 39 of their papers we have counts for
7 papers · 2 filters
Factorization and pseudofactorization of weighted graphs
Kristin Sheridan, Joseph Berleant, Mark Bathe +2
For unweighted graphs, finding isometric embeddings is closely related to decompositions of into Cartesian products of smaller graphs. When is isomorphic to a Cartesian gra…
Better Lower Bounds for Shortcut Sets and Additive Spanners via an Improved Alternation Product
Kevin Lu, Virginia Vassilevska Williams, Nicole Wein +1
We obtain improved lower bounds for additive spanners, additive emulators, and diameter-reducing shortcut sets. Spanners and emulators are sparse graphs that approximately preserve…
Improved Approximation for Longest Common Subsequence over Small Alphabets
Shyan Akmal, Virginia Vassilevska Williams
This paper investigates the approximability of the Longest Common Subsequence (LCS) problem. The fastest algorithm for solving the LCS problem exactly runs in essentially quadratic…
Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths
Yuzhou Gu, Adam Polak, Virginia Vassilevska Williams +1
One of the most basic graph problems, All-Pairs Shortest Paths (APSP) is known to be solvable in time, and it is widely open whether it has an time algori…
Hardness of Token Swapping on Trees
Oswin Aichholzer, Erik D. Demaine, Matias Korman +6
Given a graph where every vertex has exactly one labeled token, how can we most quickly execute a given permutation on the tokens? In (sequential) token swapping, the goal is to us…
Fine-Grained Complexity and Algorithms for the Schulze Voting Method
Krzysztof Sornat, Virginia Vassilevska Williams, Yinzhan Xu
We study computational aspects of a well-known single-winner voting rule called the Schulze method [Schulze, 2003] which is used broadly in practice. In this method the voters give…
Algorithms, Reductions and Equivalences for Small Weight Variants of All-Pairs Shortest Paths
Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu
APSP with small integer weights in undirected graphs [Seidel'95, Galil and Margalit'97] has an time algorithm, where is the matrix multiplication exponen…