2 papers
cs.DS2026
Performance bounds for nearest neighbor search with k-d trees
Marco Bazzani, Sanjoy Dasgupta
The -d tree is one of the oldest and most widely used data structures for nearest neighbor search. It partitions Euclidean space into axis-aligned rectangular cells. There are t…
cs.LG2025
Low-Precision Streaming PCA
Sanjoy Dasgupta, Syamantak Kumar, Shourya Pandey +1
Low-precision streaming PCA estimates the top principal component in a streaming setting under limited precision. We establish an information-theoretic lower bound on the quantizat…