Showing cs.DSShow all
3 papers · 1 filter
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
On Differential Privacy for Adaptively Solving Search Problems via Sketching
Shiyuan Feng, Ying Feng, George Z. Li +3
Recently differential privacy has been used for a number of streaming, data structure, and dynamic graph problems as a means of hiding the internal randomness of the data structure…
cs.DS2024
Fast White-Box Adversarial Streaming Without a Random Oracle
Ying Feng, Aayush Jain, David P. Woodruff
Recently, the question of adversarially robust streaming, where the stream is allowed to depend on the randomness of the streaming algorithm, has gained a lot of attention. In this…