15 papers
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…
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…
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…