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
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
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
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)
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
Quantitative Correlation Inequalities via Semigroup Interpolation
with Anindya De and Rocco Servedio
ITCS 2021 Probab. Theory Related Fields 2022 arXiv Slides Video (30 min)
Testing Sumsets is Hard
with Xi Chen, Tim Randolph, Rocco Servedio and Or Zamir
arXiv
Testing Junta Truncation
with William He
arXiv