31 citations · 35 across the 8 of their papers we have counts for
14 papers
Algorithms and Lower Bounds for Replacement Paths under Multiple Edge Failures
Virginia Vassilevska Williams, Eyob Woldeghebriel, Yinzhan Xu
This paper considers a natural fault-tolerant shortest paths problem: for some constant integer , given a directed weighted graph with no negative cycles and two fixed vertices…
Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds
Surya Mathialagan, Virginia Vassilevska Williams, Yinzhan Xu
The AP-LCA problem asks, given an -node directed acyclic graph (DAG), to compute for every pair of vertices and in the DAG a lowest common ancestor (LCA) of and …
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 SUM hypothesis, the APSP hypothesis and SETH are the three main hypotheses in fine-grained complexity. So far, within the area, the first two hypotheses have mainly been abo…
All-Pairs Shortest Path Distances with Differential Privacy: Improved Algorithms for Bounded and Unbounded Weights
Justin Y. Chen, Shyam Narayanan, Yinzhan Xu
We revisit the problem of privately releasing the all-pairs shortest path distances of a weighted undirected graph up to low additive error, which was first studied by Sealfon [Sea…
Tight Dynamic Problem Lower Bounds from Generalized BMM and OMv
Ce Jin, Yinzhan Xu
The main theme of this paper is using -dimensional generalizations of the combinatorial Boolean Matrix Multiplication (BMM) hypothesis and the closely-related Online Matrix Vect…
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…