4 papers
Learning Partition Trees for Nearest Neighbor Search
Sanjeev Khanna, Ashwin Padaki, Erik Waingarten
We study nearest neighbor search from the perspective of data-driven algorithm design: given a dataset of size and sample access to a query distributio…
Improved Approximation Algorithms for Capacitated Network Design and Flexible Graph Connectivity
Ishan Bansal, Joseph Cheriyan, Sanjeev Khanna +1
We present improved approximation algorithms for some problems in the related areas of Capacitated Network Design and Flexible Graph Connectivity. In the Cap--ECSS problem, we a…
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…
Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness
Sanjeev Khanna, Ashwin Padaki, Erik Waingarten
We initiate the study of approximation algorithms and computational barriers for constructing sparse -navigable graphs [IX23, DGM+24], a core primitive underlying recent advanc…