2 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.DS2025
Generalized Flow in Nearly-linear Time on Moderately Dense Graphs
Shunhua Jiang, Michael Kapralov, Lawrence Li +1
In this paper we consider generalized flow problems where there is an -edge -node directed graph and each edge has a loss factor governing whe…