I am a Simons–Berkeley Research Fellow at UC Berkeley. I will be an Instructor in Applied Mathematics (postdoc) at MIT starting Fall 2024.

I completed my PhD in the theory group at Columbia, where I was extremely fortunate to be advised by Rocco Servedio and Mihalis Yannakakis. Here are my research interests.

Email: shivamn@mit.edu       Office: 2-376

Research

In my field, we generally order authors alphabetically by last name. The papers below are listed in reverse-chronological order, with conference or journal versions marked in red. Here are links to my Google Scholar and DBLP pages.

PhD Thesis: A Complexity-Theoretic Perspective on Convex Geometry
Bonus 1   Bonus 2

2024

Gaussian Approximation of Convex Sets by Intersections of Halfspaces
with Anindya De and Rocco Servedio
FOCS 2024 (to appear)   arXiv

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

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

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

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

Testing Intersecting and Union-Closed Families
with Xi Chen, Anindya De, Yuhao Li and Rocco Servedio
ITCS 2024   arXiv   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   arXiv

2023

Testing Convex Truncation
with Anindya De and Rocco Servedio
SODA 2023   arXiv   Video (60 min)

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

2022

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

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

2021

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

Preprints and Manuscripts

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

Testing Junta Truncation
with William He
arXiv