Ashwin Padaki
apadaki (at) engineering.upenn.edu
I am a Computer Science Ph.D. student at the University of Pennsylvania, where I am lucky to be advised by Erik Waingarten and Sanjeev Khanna. I use ideas and tools from theoretical computer science to better understand problems that arise in machine learning and search systems, such as nearest neighbor search, quantization, and attention. My overarching goal is to develop algorithmic approaches that are theoretically principled while aligning with the constraints and objectives of real-world systems.
I spent Summer 2026 interning at Pinecone, where I developed VQ-bench, an open-source vector quantization benchmark.
Before Penn, I studied Math and Computer Science at Columbia University. I was fortunate to have amazing mentors in Josh Alman, Karthik C. S., and Rocco Servedio. My research is supported by an NSF Graduate Research Fellowship.
Papers
- Attention via Black-Box Vector Search with Alexandr Andoni, Krish Singal, Styopa Zharkov
- A Near-Optimal Space Lower Bound for Euclidean Diameter Estimation in Dynamic Streams with Krish Singal, Erik Waingarten
- Prune, Don't Rebuild: Efficiently Tuning α-Reachable Graphs for Nearest Neighbor Search with Zachary Ives, Jiaming Liang, Erik Waingarten, Tian ZhangNeurIPS 2026
- VQ-bench: A Composable Vector Quantization Framework with Amir Ingber, Edo Liberty
We propose a compositional framework for vector quantization that expresses quantizers as chains of shared algorithmic primitives. Our framework clarifies the relationships between existing methods, enables faithful comparisons, and makes it easier to design new quantizers. We implement the framework and an evaluation harness in an open-source library, and we publish a benchmark at vq-bench.com.
- Learning Partition Trees for Nearest Neighbor Search with Sanjeev Khanna, Erik Waingarten
We study nearest neighbor search from a data-driven perspective. We imagine an algorithm designer who is given a dataset and samples of past queries, with the goal of building an optimal data structure (within a class) for future queries. We focus on the class of balanced halfspace partition trees and show that, for Gaussian-like distributions, one can efficiently learn a data structure achieving sublinear query time.
- Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness with Sanjeev Khanna, Erik Waingarten
We study the problem of building the sparsest navigable graph on a dataset, an abstraction of graph-based nearest neighbor methods such as DiskANN and HNSW. We formulate navigability as a set cover problem, obtaining a cubic-time approximation algorithm and matching hardness. We then introduce a relaxation that can be solved via fast matrix multiplication.
- A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams with Sanjeev Khanna, Krish Singal, Erik Waingarten
- Inapproximability of Maximum Diameter Clustering for Few Clusters with Karthik C. S., Henry Fleischmann, Kyrylo Karlov, Styopa Zharkov
- Smaller Low-Depth Circuits for Kronecker Powers with Josh Alman, Yunfeng Guan
By convention, co-authors are listed alphabetically by last name.
Other
- Years ago, I interned as a quantitative trader at Optiver, an options market-making firm in Chicago.
- Outside of research, I like playing soccer and tennis, going on long walks and hikes, making music, and experimenting with wordplay.