93 citations · 174 across the 42 of their papers we have counts for
9 papers · 1 filter
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…
An algorithm for -set cover
Josh Alman, Baitian Li, Kevin Pratt
We show that set cover on a universe of size and with sets of size at most can be solved in time . This improves on a -time alg…
Superlogarithmic-Rank Matrix Rigidity for the Walsh-Hadamard Transform
Josh Alman
For sufficiently large which is a power of 2, we prove that changing at most one percent of the entries of the Walsh-Hadamard Transform cannot reduce its rank over…
Asymptotic Rank Speedup Theorems, Revisited
Josh Alman, Baitian Li
Motivated by fast matrix multiplication and recent connections between asymptotic tensor rank and fine-grained complexity, we revisit classical tools from the matrix multiplication…
The edge of the asymptotic spectrum of tensors
Josh Alman, Baitian Li, Kevin Pratt
Strassen founded the theory of the asymptotic spectrum of tensors to study the complexity of matrix multiplication. A central challenge in this theory is to explicitly construct ne…
Learning Functions of Halfspaces
Josh Alman, Shyamal Patel, Rocco A. Servedio
We give an algorithm that learns arbitrary Boolean functions of arbitrary halfspaces over , in the challenging distribution-free Probably Approximately Correct (P…
Every Bit Counts: A Theoretical Study of Precision-Expressivity Tradeoffs in Quantized Transformers
Sayak Chakrabarti, Toniann Pitassi, Josh Alman
Quantization reduces the numerical precision of Transformer computations and is widely used to accelerate inference, yet its effect on expressivity remains poorly characterized. We…
Poly-attention: a general scheme for higher-order self-attention
Sayak Chakrabarti, Toniann Pitassi, Josh Alman
The self-attention mechanism, at the heart of the Transformer model, is able to effectively model pairwise interactions between tokens. However, numerous recent works have shown th…