Shivam Nadimpalli

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: Office: 2-376

Research

My research lies broadly at the interface of complexity theory and high-dimensional geometry, probability, and statistics. Some questions that motivate my work include:

  • Which forms of structure (such as convexity, low-dimensionality, or sparsity) can we efficiently recognize and exploit in high-dimensional settings?
  • When can complex high-dimensional objects be usefully approximated by simpler, sparse, or lower-dimensional ones?
  • When do these tasks admit efficient algorithms, and when are they computationally intractable?

Selected Papers

Sparsifying Suprema of Gaussian Processes v2with Anindya De, Ryan O'Donnell and Rocco ServedioSTOC 2026

Gaussian Approximation of Convex Sets by Intersections of Halfspaceswith Anindya De and Rocco ServedioFOCS 2024

Optimal Non-Adaptive Tolerant Junta Testing via Local Estimatorswith Shyamal PatelSTOC 2024

Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntaswith Xi Chen, Anindya De, Yuhao Li and Rocco ServedioSODA 2024

Quantitative Correlation Inequalities via Semigroup Interpolationwith Anindya De and Rocco ServedioProbab. Theory Related Fields 2022

Service

Miscellaneous

I enjoy being outdoors, cooking, and staring at my cat.