3 papers
cs.LG2026
Streaming Attention Approximation via Discrepancy Theory
Ekaterina Kochetkova, Kshiteej Sheth, Insu Han +2
Large language models (LLMs) have achieved impressive success, but their high memory requirements present challenges for long-context token generation. In this paper we study the s…
cs.DS2025
Sublinear Time Low-Rank Approximation of Hankel Matrices
Michael Kapralov, Cameron Musco, Kshiteej Sheth
Hankel matrices are an important class of highly-structured matrices, arising across computational mathematics, engineering, and theoretical computer science. It is well-known that…
cs.LG2025
Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions
Piotr Indyk, Michael Kapralov, Kshiteej Sheth +1
Motivated by the problem of fast processing of attention matrices, we study fast algorithms for computing matrix-vector products for asymmetric Gaussian Kernel matrices $K\in \math…