31 citations · 35 across the 22 of their papers we have counts for
7 papers · 1 filter
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 voters and candidates, it…
Removing Additive Structure in 3SUM-Based Reductions
Ce Jin, Yinzhan Xu
Our work explores the hardness of SUM instances without certain additive structures, and its applications. As our main technical result, we show that solving SUM on a size-$n…
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…