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