93 citations · 174 across the 42 of their papers we have counts for
5 papers · 1 filter
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…
Tensor Ranks and the Fine-Grained Complexity of Dynamic Programming
Josh Alman, Ethan Turok, Hantao Yu +1
Generalizing work of Künnemann, Paturi, and Schneider [ICALP 2017], we study a wide class of high-dimensional dynamic programming (DP) problems in which one must find the shortest…
Matrix Multiplication and Number On the Forehead Communication
Josh Alman, Jarosław Błasiok
Three-player Number On the Forehead communication may be thought of as a three-player Number In the Hand promise model, in which each player is given the inputs that are supposedly…
Fast Attention Requires Bounded Entries
Josh Alman, Zhao Song
In modern machine learning, inner product attention computation is a fundamental task for training large language models such as Transformer, GPT-1, BERT, GPT-2, GPT-3 and ChatGPT.…