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