4 papers
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…
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…
Spectral Clustering in Birthday Paradox Time
Michael Kapralov, Ekaterina Kochetkova, Weronika Wrzos-Kaminska
Given a vertex in a -clusterable graph, i.e. a graph whose vertex set can be partitioned into a disjoint union of -expanders of size with outer condu…
Spectral Clustering with Side Information
Hendrik Fichtenberger, Michael Kapralov, Ekaterina Kochetkova +3
In the graph clustering problem with a planted solution, the input is a graph on vertices partitioned into clusters, and the task is to infer the clusters from graph struct…