49 citations · 193 across the 39 of their papers we have counts for
8 papers · 1 filter
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 +1
A recent and active line of work achieves tight lower bounds for fundamental problems under the Strong Exponential Time Hypothesis (SETH). A celebrated result of Backurs and Indyk…
A 7/3-Approximation for Feedback Vertex Sets in Tournaments
Matthias Mnich, Virginia Vassilevska Williams, László A. Végh
We consider the minimum-weight feedback vertex set problem in tournaments: given a tournament with non-negative vertex weights, remove a minimum-weight set of vertices that interse…
Who Can Win a Single-Elimination Tournament?
Michael P. Kim, Warut Suksompong, Virginia Vassilevska Williams
A single-elimination (SE) tournament is a popular way to select a winner in both sports competitions and in elections. A natural and well-studied question is the tournament fixing…
Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter
Amir Abboud, Virginia Vassilevska Williams, Joshua Wang
The radius and diameter are fundamental graph parameters. They are defined as the minimum and maximum of the eccentricities in a graph, respectively, where the eccentricity of a ve…
Very Sparse Additive Spanners and Emulators
Greg Bodwin, Virginia Vassilevska Williams
We study two popular ways to sketch the shortest path distances of an input graph. The first is distance preservers, which are sparse subgraphs that agree with the distances of the…
Better Distance Preservers and Additive Spanners
Greg Bodwin, Virginia Vassilevska Williams
We study two popular ways to sketch the shortest path distances of an input graph. The first is distance preservers, which are sparse subgraphs that agree with the distances of the…