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 do research in theoretical computer science, with an emphasis on sublinear algorithms and high-dimensional geometry. Here are links to my Google Scholar and DBLP pages.

2025

Faster Exact Learning of k-term DNFs with Membership and Equivalence Queries
with Josh Alman, Rocco Servedio and Shyamal Patel
FOCS 2025

DNF Learning via Locally Mixing Random Walks
with Josh Alman, Rocco Servedio and Shyamal Patel
STOC 2025

Lower Bounds for Convexity Testing
with Xi Chen, Anindya De, Rocco Servedio and Erik Waingarten
SODA 2025

Relative-Error Monotonicity Testing
with Xi Chen, Anindya De, Yizhi Huang, Yuhao Li, Rocco Servedio and Tianqi Yang
SODA 2025

Testing Sumsets is Hard
with Xi Chen, Rocco Servedio, Tim Randolph and Or Zamir
ESA 2025

2024

Gaussian Approximation of Convex Sets by Intersections of Halfspaces
with Anindya De and Rocco Servedio
FOCS 2024

A Counterexample to a Directed KKL Inequality
with Quentin Dubroff and Bhargav Narayanan
Electron. J. Combin. 2024

Detecting Low-Degree Truncation v2
with Anindya De, Huan Li and Rocco Servedio
STOC 2024   Video (15 min)

Optimal Non-Adaptive Tolerant Junta Testing via Local Estimators
with Shyamal Patel
STOC 2024   Video (15 min)

On the Pauli Spectrum of QAC0
with Natalie Parham, Francisca Vasconcelos and Henry Yuen
STOC 2024   QIP 2024   Video (20 min)

Testing Intersecting and Union-Closed Families
with Xi Chen, Anindya De, Yuhao Li and Rocco Servedio
ITCS 2024   Video (20 min)

Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas
with Xi Chen, Anindya De, Yuhao Li and Rocco Servedio
SODA 2024

2023

Testing Convex Truncation v2
with Anindya De and Rocco Servedio
SODA 2023   Math. Stat. Learn. 2025   Video (60 min)

Testing and Learning Quantum Juntas Nearly Optimally
with Thomas Chen and Henry Yuen
SODA 2023   QIP 2023   Video (25 min)

2022

Convex Influences
with Anindya De and Rocco Servedio
ITCS 2022   Video (30 min)

Approximating Sumset Size
with Anindya De and Rocco Servedio
SODA 2022   Slides

2021

Quantitative Correlation Inequalities via Semigroup Interpolation
with Anindya De and Rocco Servedio
ITCS 2021   Probab. Theory Related Fields 2022   Slides   Video (30 min)

PhD Thesis

A Complexity-Theoretic Perspective on Convex Geometry
Academic Commons   Bonus 1   Bonus 2
See [DNOS'24] and [DNS'24] for updated versions of Chapters 6 and 8 respectively.