Shivam Nadimpalli

Email:

I am a PhD student in the theory group at Columbia, where I am extremely fortunate to be advised by Rocco Servedio and Mihalis Yannakakis.

Here are links to my CV and my research interests.

Publications

In my field, we generally order authors alphabetically by last name. Here are links to my Google Scholar and DBLP pages.

• Detecting Low-Degree Truncation
  with Anindya De, Huan Li and Rocco Servedio
  [arXiv] STOC 2024
• Optimal Non-Adaptive Tolerant Junta Testing via Local Estimators
  with Shyamal Patel
  STOC 2024
• On the Pauli Spectrum of QAC⁰
  with Natalie Parham, Francisca Vasconcelos and Henry Yuen
  [arXiv] STOC 2024, QIP 2024
• Testing Intersecting and Union-Closed Families
  with Xi Chen, Anindya De, Yuhao Li and Rocco Servedio
  [arXiv] [video] ITCS 2024
• Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas
  with Xi Chen, Anindya De, Yuhao Li and Rocco Servedio
  [arXiv] SODA 2024
• Testing Convex Truncation
  with Anindya De and Rocco Servedio
  [arXiv] [video] SODA 2023
• Testing and Learning Quantum Juntas Nearly Optimally
  with Thomas Chen and Henry Yuen
  [arXiv] [slides] SODA 2023, QIP 2023
• Convex Influences
  with Anindya De and Rocco Servedio
  [arXiv] [slides, video] ITCS 2022
• Approximating Sumset Size
  with Anindya De and Rocco Servedio
  [arXiv] [slides] SODA 2022
• Quantitative Correlation Inequalities via Semigroup Interpolation
  with Anindya De and Rocco Servedio
  [arXiv, journal] [slides, video] ITCS 2021, Probability Theory and Related Fields 2022

Preprints and Manuscripts

• Gaussian Approximation of Convex Sets by Intersections of Halfspaces
  with Anindya De and Rocco Servedio
  [arXiv]
• A Counterexample to a Directed KKL Inequality
  with Quentin Dubroff and Bhargav Narayanan
  [arXiv]
• Testing Junta Truncation
  with William He
  [arXiv]
• Testing Sumsets is Hard
  with Xi Chen, Tim Randolph, Rocco Servedio and Or Zamir
  [arXiv]

Teaching

I have served as a TA for the following classes at Columbia:

• COMS 4236 Introduction to Computational Complexity (Spring 2022)
• COMS 4252 Introduction to Computational Learning Theory (Spring 2021)

I am also passionate about STEM outreach: I have taught Fun with Mathematical Inequalities as a part of the Science Honors Program, and have served as a mentor for the Undergraduate TCS Learning Seminar at Columbia.

Miscellaneous

• I organized a reading group on topics in Boolean function analysis.
• I am an alum of the Budapest Semesters in Mathematics, where I scribed notes for Advanced Algebra.
• I really like bagels.