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, high-dimensional geometry, and probability theory. Across these areas, I'm particularly interested in finding useful, interpretable descriptions of complex data. This might mean identifying a small set of relevant variables or learning a simple prediction rule, such as a linear classifier. I design algorithms that work under weak modeling assumptions, as well as efficient methods for testing whether these assumptions hold.
For my papers, see my full publication list, Google Scholar, or DBLP.
Recent & Selected Publications
Efficient Proper Agnostic Learning of Halfspaces
Preprint
An efficient query algorithm for finding a nearly best-fitting linear classifier to an unknown Boolean function. Gives the first running-time improvement over polynomial regression (Kalai et al., FOCS 2005).
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 participated in Harvard CMSA's "Math Research in the Age of AI" summit with 31 other mathematicians; I encourage you to read our report.
- 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.
