Shivam Nadimpalli

Hello! I am an Instructor in Applied 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. 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
Academic Commons Bonus 1 Bonus 2
See [DNOS'24] and [DNS'24] for updated versions of Chapters 6 and 8 respectively.

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

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 QAC⁰
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