Poojan Shah

Hi, Stranger! Welcome to my corner of the internet.

I am an upcoming AI Research Scientist at Mistral. I recently graduated from the Department of Computer Science & Engineering at IIT Delhi, where I worked on algorithms for clustering problems with Ragesh Jaiswal.

I enjoy thinking about the design and analysis of algorithms related (and unrelated) to the practice of modern information processing. Much of my work explores how structural assumptions can break through worst-case computational barriers.

During my undergraduate years, I spent many memorable summers with Rahul Jain in the Computer Science Group at the Centre for Quantum Technologies, Singapore, where I studied cryptographic primitives based on pseudorandom quantum states; with Makarand Tapaswi at Wadhwani AI, where I worked on training VAEs for self-supervised learning from unlabeled data for newborn anthropometry; and at Atlas Research as a quantitative trading and research intern. I also visited the Faculty of Mathematics at the University of Waterloo for a semester as an exchange student.

Outside research, I am a percussionist with a particular interest in Indian classical instruments, and occasionally write.

Publications

Noisy k-means++ is Not too Noisy

Poojan Shah

Preprint - In submission.

commentary arXiv

What began as a question about whether k-means++ is genuinely robust to small errors in its sampling probabilities turned out to have a rather surprising history: the best previous analysis either lost an extra \(\log k\) factor or a constant of approximately 147,638, even as the noise went to zero. I realised that the obstruction becomes much cleaner if, instead of trying to control the average cost directly, one studies the entire cumulative distribution of cluster costs. A high-low statistic at every threshold forms a supermartingale, and integrating these inequalities recovers the average. This gives a \(1+O(\varepsilon)\) loss over classical k-means++, which I also show is asymptotically necessary. Interestingly, if pointwise multiplicative error is weakened to total-variation closeness, no finite guarantee is possible even for \(k=2\).

Fast k-means seeding under the manifold hypothesis

Poojan Shah, Shashwat Agrawal, and Ragesh Jaiswal

ICML 2026 — Forty-Third International Conference on Machine Learning

commentary arXiv OpenReview Poster

What began as a conversation about whether D²-sampling could be used to estimate the intrinsic dimension of data eventually led to a sampling algorithm that is provably fast on data with low intrinsic dimension. This is particularly interesting in light of the growing empirical evidence that high-dimensional machine learning datasets often have low intrinsic dimension, consistent with the manifold hypothesis. Our variant of D²-sampling is provably fast for data satisfying certain scaling laws, which can be theoretically motivated by the manifold hypothesis. Interestingly, after extensive checks across a wide range of datasets, we found that these scaling laws appear to be remarkably prevalent!

Quantum (inspired) D²-sampling with applications

Poojan Shah and Ragesh Jaiswal

ICLR 2025 — Thirteenth International Conference on Learning Representations

commentary arXiv OpenReview Poster

We designed a quantum algorithm for D²-sampling (and through this, the first quantum approximation scheme for k-means with polylogarithmic running time in the Quantum RAM (QRAM) model) only to realise that (to put it bluntly in the words of a reviewer-2) "there is not much quantum here". This made us realise that, as with so many other Quantum Machine Learning (QML) algorithms in the QRAM model, our D²-sampling-based quantum clustering algorithms can also be dequantized in the sample-query access model of Ewin Tang (PhD Thesis) to obtain a classical algorithm without much loss in the running time (unlike other QML dequantization results where there is a significant loss). We then realised that the dequantization, results in a fast implementation of k-means++, which has a lot of practical value.

Selected Honours

Suresh Chandra Memorial Trust Award

Department of Computer Science and Engineering, IIT Delhi, 2026

context Award Record Convocation Brochure

Received for the best B.Tech. software project in IIT Delhi's graduating Computer Science and Engineering class of 2026.

Outstanding Teaching Assistant Award

Department of Computer Science and Engineering, IIT Delhi, 2026

context IIT Delhi CSE

Recognized by the CSE department for my work as Head Teaching Assistant for COL7160: Quantum Computing in Winter 2026.

Amit and Deepali Sinha Foundation Fellowship

IIT Delhi, 2022

context Fellowship Record Full-Ride Announcement About JEE Advanced

Selected as one of five incoming IIT Delhi undergraduates for a four-year full-ride fellowship awarded on the basis of JEE Advanced rank and continued academic standing. I was placed 67th nationally in JEE Advanced 2022, the competitive examination used for undergraduate admission to the Indian Institutes of Technology.

Talks

Quantum and Quantum Inspired Classical Algorithms for Clustering

CS Group Meeting CQT - NUS, April 20, 2025

Poster

Quantum Machine Learning without any Quantum

TCS Seminar, IIT Delhi — Bharti 501, November 4, 2024

Slides

Teaching

Head Teaching Assistant for COL7160 : Quantum Computing, Winter 2026. Received the Outstanding Teaching Assistant Award.