93 citations · 174 across the 42 of their papers we have counts for
6 papers · 1 filter
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…