4 papers
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…
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…