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