Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
Attention via Black-Box Vector Search
Stepan Zharkov, Krish Singal, Ashwin Padaki +1
Sparse attention mechanisms estimate attention over tokens using a small subset of keys. Many existing approaches use maximum inner product search (MIPS) to retrieve the heavie…
cs.DS2026
Fast Geometric Spanners via Approximate Nearest Neighbor Search
Alexandr Andoni, Manuel Paez, Krish Singal +1
We study the problem of constructing metric spanners in general metric spaces in subquadratic time when given blackbox access to a fast algorithm for batch approximate nearest neig…
cs.DS2025
A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
Sanjeev Khanna, Ashwin Padaki, Krish Singal +1
We study the space complexity of estimating the diameter of a subset of points in an arbitrary metric space in the dynamic (turnstile) streaming model. The input is given as a stre…