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.
In summer 2026, I interned at Pinecone, hosted by Amir Ingber and Edo Liberty. We developed and maintain VQ-bench, an open-source benchmark for vector quantization.
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
Vector quantization is increasingly important for vector databases and LLMs, but state-of-the-art approaches are hard to compare. We propose a framework that expresses quantizers as compositions of shared primitives, making it easy to compare existing approaches and design new ones. We provide an open-source library for building and evaluating quantizers, along with a public benchmark at vq-bench.com.
- Learning Partition Trees for Nearest Neighbor Search with Sanjeev Khanna, Erik Waingarten
Can a nearest neighbor search index learn from past queries to answer future ones more efficiently? We give a positive answer: whenever queries follow a Gaussian-like distribution and the dataset admits a perfect halfspace partition tree, one can efficiently learn a data structure with sublinear query time.
- Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness with Sanjeev Khanna, Erik Waingarten
Graph-based nearest neighbor search requires graphs that are simultaneously sparse and easy to navigate, but just how sparse can they be? We formulate constructing the sparsest navigable graph as a set covering problem, obtaining an O(n3)-time approximation algorithm and matching hardness. We then introduce a relaxation of the problem which we solve 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
- 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.
- 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.