93 citations · 174 across the 42 of their papers we have counts for
50 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…
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…
Kronecker Powers, Orthogonal Vectors, and the Asymptotic Spectrum
Josh Alman, Baitian Li
We study circuits for computing depth-2 linear transforms defined by Kronecker power matrices. Recent works have improved on decades-old constructions in this area using a new ''re…
Faster exact learning of k-term DNFs with membership and equivalence queries
Josh Alman, Shivam Nadimpalli, Shyamal Patel +1
In 1992 Blum and Rudich [BR92] gave an algorithm that uses membership and equivalence queries to learn -term DNF formulas over in time , improv…
Two Heads Are Better than One: Simulating Large Transformers with Small Ones
Hantao Yu, Josh Alman
The quadratic complexity of self-attention prevents transformers from scaling effectively to long input sequences. On the other hand, modern GPUs and other specialized hardware acc…
DNF Learning via Locally Mixing Random Walks
Josh Alman, Shivam Nadimpalli, Shyamal Patel +1
We give two results on PAC learning DNF formulas using membership queries in the challenging "distribution-free" learning framework, where learning algorithms must succeed for an a…
Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapse
Josh Alman, Zhao Song
Attention mechanisms lie at the heart of modern large language models (LLMs). Straightforward algorithms for forward and backward (gradient) computation take quadratic time, and a…
Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform
Josh Alman, Zhao Song
The transformer architecture has been widely applied to many machine learning tasks. A main bottleneck in the time to perform transformer computations is a task called attention co…
Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification
Josh Alman, Jingxun Liang
For an matrix , its rank- rigidity, denoted , is the minimum number of entries of that one must change to make its rank become at most .…
Faster Algorithms for Average-Case Orthogonal Vectors and Closest Pair Problems
Josh Alman, Alexandr Andoni, Hengjie Zhang
We study the average-case version of the Orthogonal Vectors problem, in which one is given as input vectors from which are chosen randomly so that each coordinate i…
Improving the Leading Constant of Matrix Multiplication
Josh Alman, Hantao Yu
Algebraic matrix multiplication algorithms are designed by bounding the rank of matrix multiplication tensors, and then using a recursive method. However, designing algorithms in t…
Fundamental Limitations on Subquadratic Alternatives to Transformers
Josh Alman, Hantao Yu
The Transformer architecture is widely deployed in many popular and impactful Large Language Models. At its core is the attention mechanism for calculating correlations between pai…
Finer-Grained Hardness of Kernel Density Estimation
Josh Alman, Yunfeng Guan
In batch Kernel Density Estimation (KDE) for a kernel function , we are given as input points in dimension , as well…
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…
The Fine-Grained Complexity of Gradient Computation for Training Large Language Models
Josh Alman, Zhao Song
Large language models (LLMs) have made fundamental contributions over the last a few years. To train an LLM, one needs to alternatingly run `forward' computations and `backward' co…
Generalizations of Matrix Multiplication can solve the Light Bulb Problem
Josh Alman, Hengjie Zhang
In the light bulb problem, one is given uniformly random vectors . They are all chosen independently except a planted pair $(x_{i…
How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation
Josh Alman, Zhao Song
In the classical transformer attention scheme, we are given three size matrices (the query, key, and value tokens), and the goal is to compute a new $n \time…