9 papers
Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs
Josh Alman, Virginia Vassilevska Williams
We give the first polynomial improvements over the textbook algorithms for SUM and All-Pairs Shortest Paths (APSP): we show how to deterministically solve SUM on integers…
Improving the matrix multiplication exponent with modern optimization and AlphaEvolve
Emilien Dupont, Marvin Eisenberger, Borislav Kozlovskii +7
The current best bounds on the matrix multiplication exponent are obtained through a refinement of the laser method called combination loss analysis (Duan et al., 2022; William…
Average-Case Hardness of Parity Problems: Orthogonal Vectors, k-SUM and More
Mina Dalirrooyfard, Andrea Lincoln, Barna Saha +1
This work establishes conditional lower bounds for average-case {\em parity}-counting versions of the problems -XOR, -SUM, and -OV. The main contribution is a set of self-…
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…
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…
Listing 6-Cycles
Ce Jin, Virginia Vassilevska Williams, Renfei Zhou
Listing copies of small subgraphs (such as triangles, -cycles, small cliques) in the input graph is an important and well-studied problem in algorithmic graph theory. In this pa…
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(…
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…