31 citations · 35 across the 22 of their papers we have counts for
3 papers · 1 filter
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…
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…