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