5 papers
New Separations and Reductions for Directed Preservers and Hopsets
Gary Hoppenworth, Yinzhan Xu, Zixuan Xu
We study distance preservers, hopsets, and shortcut sets in -node, -edge directed graphs, and show improved bounds and new reductions for various settings of these problems.…
Additive Spanner Lower Bounds with Optimal Inner Graph Structure
Greg Bodwin, Gary Hoppenworth, Virginia Vassilevska Williams +2
We construct -node graphs on which any -size spanner has additive error at least , improving on the previous best lower bound of [Bodwin-Hoppenw…
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…
Improved Roundtrip Spanners, Emulators, and Directed Girth Approximation
Alina Harbuzova, Ce Jin, Virginia Vassilevska Williams +1
Roundtrip spanners are the analog of spanners in directed graphs, where the roundtrip metric is used as a notion of distance. Recent works have shown existential results of roundtr…
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(…