3 papers
cs.DS2026
Towards Tight Bounds for Streaming Attention
Justin Y. Chen, Ying Feng, Piotr Indyk +3
The attention mechanism is a cornerstone of modern transformer architectures. However, its expressive power comes at the cost of quadratic runtime and linear space usage. In partic…
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…
cs.CG2025
Even Faster Algorithm for the Chamfer Distance
Ying Feng, Piotr Indyk
For two d-dimensional point sets A, B of size up to n, the Chamfer distance from A to B is defined as CH(A,B) = \sum_{a \in A} \min_{b \in B} \|a-b\|. The Chamfer distance is a wid…