Optimal Sparsification of Gaussian Processes
Preprint video
An exponential improvement on my STOC’26 paper with Anindya De, Rocco Servedio, and Ryan O’Donnell.
Hello! I am a C.L.E. Moore Instructor of Mathematics (≈ departmental postdoc) at MIT.
I completed my PhD in the theory group at Columbia, where I was extremely fortunate to be advised by Rocco Servedio and Mihalis Yannakakis.
Email: shivamn@mit.edu Office: 2-376
Research
I study the power and limits of efficient computation in high dimensions. My work spans learning theory, sublinear algorithms, and statistics, drawing on and contributing to complexity theory (particularly the analysis of Boolean functions), high-dimensional geometry, and probability theory. A recurring theme is understanding how structure—such as convexity, low-dimensionality, or sparsity—can be detected and exploited in theoretical models inspired by practical questions.
You can find my full publication list, as well as my papers on Google Scholar and DBLP.
Recent & Selected Publications
Model-agnostic distribution recovery in high dimension via Fourier measurements
SODA 2027
Sharp bounds for recovering high-dimensional distributions from noisy Fourier measurements, without any assumptions on sparsity or separation.
Testing Noisy Low-Degree Polynomials for Sparsity
STOC 2026
A precise characterization of when sparsity can be tested from noisy examples using a number of samples independent of dimension.
Gaussian Approximation of Convex Sets by Intersections of Halfspaces
FOCS 2024 slides
How many halfspaces do you need to approximate a convex set under the Gaussian distribution? Sadly, we still don’t quite know the answer.
On the Pauli Spectrum of QAC0
STOC 2024 QIP 2024
Progress toward resolving Moore’s 1999 conjecture on the limits of shallow quantum circuits. Recently settled by OpenAI.
Quantitative Correlation Inequalities via Extremal Power Series
Probability Theory and Related Fields 2022
A general approach to quantitative correlation inequalities. Gives a simple proof of (a generalization of) Talagrand’s correlation inequality and a strengthening of Royen’s Gaussian correlation inequality.
Service
- I co-organize TCS+, an online seminar series in theoretical computer science. Suggest a talk here!
- I co-organized a workshop at STOC 2026 on Testing in the Modern World.
Miscellaneous
I enjoy being outdoors, cooking, and staring at (or being stared at by) my cat.
