31 citations · 35 across the 22 of their papers we have counts for
28 papers
Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence
Jakob Nogler, Adam Polak, Barna Saha +3
The tree edit distance (TED) between two rooted ordered trees with nodes labeled from an alphabet is the minimum cost of transforming one tree into the other by a sequence…
All-Hops Shortest Paths
Virginia Vassilevska Williams, Zoe Xi, Yinzhan Xu +1
Let be a weighted directed graph without negative cycles. For two vertices , we let be the minimum, according to the weight function , of…
Fine-Grained Optimality of Partially Dynamic Shortest Paths and More
Barna Saha, Virginia Vassilevska Williams, Yinzhan Xu +1
Single Source Shortest Paths () is among the most well-studied problems in computer science. In the incremental (resp. decremental) setting, the goal is to maintain…
More Asymmetry Yields Faster Matrix Multiplication
Josh Alman, Ran Duan, Virginia Vassilevska Williams +3
We present a new improvement on the laser method for designing fast matrix multiplication algorithms. The new method further develops the recent advances by [Duan, Wu, Zhou FOCS 20…
Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More
Ce Jin, Yinzhan Xu
In sparse convolution-type problems, a common technique is to hash the input integers modulo a random prime for some parameter , which reduces the range of the in…
Simpler and Higher Lower Bounds for Shortcut Sets
Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu
We provide a variety of lower bounds for the well-known shortcut set problem: how much can one decrease the diameter of a directed graph on vertices and edges by adding $O(…
Simpler Reductions from Exact Triangle
Timothy M. Chan, Yinzhan Xu
In this paper, we provide simpler reductions from Exact Triangle to two important problems in fine-grained complexity: Exact Triangle with Few Zero-Weight -Cycles and All-Edges…
Faster Algorithms for Text-to-Pattern Hamming Distances
Timothy M. Chan, Ce Jin, Virginia Vassilevska Williams +1
We study the classic Text-to-Pattern Hamming Distances problem: given a pattern of length and a text of length , both over a polynomial-size alphabet, compute the Ha…
Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques
Mina Dalirrooyfard, Surya Mathialagan, Virginia Vassilevska Williams +1
We study finding and listing -cliques in a graph, for constant , a fundamental problem of both theoretical and practical importance. Our main contribution is a new outp…
New Bounds for Matrix Multiplication: from Alpha to Omega
Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu +1
The main contribution of this paper is a new improved variant of the laser method for designing matrix multiplication algorithms. Building upon the recent techniques of [Duan, Wu,…
Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More
Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu
In this paper we carefully combine Fredman's trick [SICOMP'76] and Matoušek's approach for dominance product [IPL'91] to obtain powerful results in fine-grained complexity: - Under…
Optimal Bounds for Noisy Sorting
Yuzhou Gu, Yinzhan Xu
Sorting is a fundamental problem in computer science. In the classical setting, it is well-known that comparisons are both necessary and sufficient to sort…
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…
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…
Monochromatic Triangles, Triangle Listing and APSP
Virginia Vassilevska Williams, Yinzhan Xu
One of the main hypotheses in fine-grained complexity is that All-Pairs Shortest Paths (APSP) for -node graphs requires time. Another famous hypothesis is that the…
Faster Dynamic Range Mode
Bryce Sandlund, Yinzhan Xu
In the dynamic range mode problem, we are given a sequence of length bounded by and asked to support element insertion, deletion, and queries for the most frequent element…