7 papers
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…
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…
Inner Product Aware Quantization: Provably Fast, Accurate, and Adaptive Algorithms
Nathan White, Krish Singal
Quantization is a fundamental tool used to compress datasets, neural network weights, and memory usage in a range of computational tasks. Many downstream applications of vector qua…
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…
Chip-Firing Games on Banana Trees
Marchelle Beougher, Nila Cibu, Kexin Ding +6
We study chip-firing games on multigraphs whose underlying simple graphs are trees, paths, and stars, denoted as banana trees, paths, and stars respectively. We present a polynomia…
The gonality of chess graphs
Nila Cibu, Kexin Ding, Steven DiSilvio +4
Chess graphs encode the moves that a particular chess piece can make on an chessboard. We study through these graphs through the lens of chip-firing games and graph gon…
On the size and complexity of scrambles
Seamus Connor, Steven DiSilvio, Sasha Kononova +2
The scramble number of a graph, a natural generalization of bramble number, is an invariant recently developed to study chip-firing games and graph gonality. We introduce the carto…