My research lies broadly at the interface of theoretical computer science, high-dimensional geometry, probability, and statistics. Here are links to my Google Scholar and DBLP pages. Feel free to email me with any comments, feedback, or questions!

Authorship is alphabetical as per convention in mathematics and theoretical computer science.

Optimal Sparsification of Gaussian ProcessesShivam Nadimpalli(Preprint)

No Price Tags? No Problem: Query Strategies for Unpriced InformationShivam Nadimpalli, Mingda Qiao, and Ronitt Rubinfeld(Preprint)

Model-Agnostic Super-Resolution in High-DimensionsXi Chen, Anindya De, Yizhi Huang, Shivam Nadimpalli, Rocco Servedio, and Tianqi Yang(Preprint)

Learning and Testing Convex FunctionsRenato Ferreira Pinto Jr., Cassandra Marcussen, Elchanan Mossel, and Shivam Nadimpalli(Preprint)

Testing Noisy Low-Degree Polynomials for SparsityYiqiao Bao, Anindya De, Shivam Nadimpalli, Rocco Servedio, and Nathan WhiteSTOC 2026

Sparsifying Suprema of Gaussian Processes v2Anindya De, Shivam Nadimpalli, Ryan O'Donnell, and Rocco ServedioSTOC 2026   slides

On the Maximal Gaussian Perimeter of Convex Sets, RevisitedShivam Nadimpalli and Caleb PascaleGAFA Seminar Notes 2026

Halfspaces are Hard to Test with Relative ErrorXi Chen, Anindya De, Yizhi Huang, Shivam Nadimpalli, Rocco Servedio, and Tianqi YangSODA 2026

Sublinear-Query Relative-Error Testing of HalfspacesXi Chen, Anindya De, Yizhi Huang, Shivam Nadimpalli, Rocco Servedio, and Tianqi YangICALP 2026

Faster Exact Learning of k-term DNFs with Membership and Equivalence QueriesJosh Alman, Shivam Nadimpalli, Shyamal Patel, and Rocco ServedioFOCS 2025

DNF Learning via Locally Mixing Random WalksJosh Alman, Shivam Nadimpalli, Shyamal Patel, and Rocco ServedioSTOC 2025

Lower Bounds for Convexity TestingXi Chen, Anindya De, Shivam Nadimpalli, Rocco Servedio, and Erik WaingartenSODA 2025

Relative-Error Monotonicity TestingXi Chen, Anindya De, Yizhi Huang, Yuhao Li, Shivam Nadimpalli, Rocco Servedio, and Tianqi YangSODA 2025

Testing Sumsets is HardXi Chen, Shivam Nadimpalli, Tim Randolph, Rocco Servedio, and Or ZamirESA 2025

Gaussian Approximation of Convex Sets by Intersections of HalfspacesAnindya De, Shivam Nadimpalli, and Rocco ServedioFOCS 2024

A Counterexample to a Directed KKL InequalityQuentin Dubroff, Shivam Nadimpalli, and Bhargav NarayananElectron. J. Combin. 2024

Detecting Low-Degree Truncation v2Anindya De, Huan Li, Shivam Nadimpalli, and Rocco ServedioSTOC 2024   video

Optimal Non-Adaptive Tolerant Junta Testing via Local EstimatorsShivam Nadimpalli and Shyamal PatelSTOC 2024   video

On the Pauli Spectrum of QAC⁰Shivam Nadimpalli, Natalie Parham, Francisca Vasconcelos, and Henry YuenSTOC 2024   QIP 2024   video

Testing Intersecting and Union-Closed FamiliesXi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, and Rocco ServedioITCS 2024   video

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

Testing Convex Truncation v2Anindya De, Shivam Nadimpalli, and Rocco ServedioSODA 2023   Math. Stat. Learn. 2025   video

Testing and Learning Quantum Juntas Nearly OptimallyThomas Chen, Shivam Nadimpalli, and Henry YuenSODA 2023   QIP 2023   video

Convex InfluencesAnindya De, Shivam Nadimpalli, and Rocco ServedioITCS 2022   video

Approximating Sumset SizeAnindya De, Shivam Nadimpalli, and Rocco ServedioSODA 2022   slides

Quantitative Correlation Inequalities via Semigroup InterpolationAnindya De, Shivam Nadimpalli, and Rocco ServedioITCS 2021   Probab. Theory Related Fields 2022   slides   video

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

Testing Junta TruncationWilliam He and Shivam NadimpalliSubsumed by [BHS'26].