Shivam Nadimpalli

According to our database, Shivam Nadimpalli authored at least 20 papers between 2021 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2025

Faster exact learning of k-term DNFs with membership and equivalence queries.

Josh Alman, Shivam Nadimpalli, Shyamal Patel, Rocco A. Servedio

CoRR, July, 2025

DNF Learning via Locally Mixing Random Walks.

Josh Alman, Shivam Nadimpalli, Shyamal Patel, Rocco A. Servedio

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Lower Bounds for Convexity Testing.

Xi Chen, Anindya De, Shivam Nadimpalli, Rocco A. Servedio, Erik Waingarten

Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 2025

Relative-error monotonicity testing.

Xi Chen, Anindya De, Yizhi Huang, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio, Tianqi Yang

Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 2025

2024

A Complexity-Theoretic Perspective on Convex Geometry

Shivam Nadimpalli

PhD thesis, 2024

Sparsifying Suprema of Gaussian Processes.

Anindya De, Shivam Nadimpalli, Ryan O'Donnell, Rocco A. Servedio

CoRR, 2024

Testing Sumsets is Hard.

Xi Chen, Shivam Nadimpalli, Tim Randolph, Rocco A. Servedio, Or Zamir

CoRR, 2024

A Counterexample to a Directed KKL Inequality.

Quentin Dubroff, Shivam Nadimpalli, Bhargav Narayanan

Electron. J. Comb., 2024

On the Pauli Spectrum of QAC0.

Shivam Nadimpalli, Natalie Parham, Francisca Vasconcelos, Henry Yuen

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Optimal Non-adaptive Tolerant Junta Testing via Local Estimators.

Shivam Nadimpalli, Shyamal Patel

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Detecting Low-Degree Truncation.

Anindya De, Huan Li, Shivam Nadimpalli, Rocco A. Servedio

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas.

Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Testing Intersecting and Union-Closed Families.

Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

Gaussian Approximation of Convex Sets by Intersections of Halfspaces.

Anindya De, Shivam Nadimpalli, Rocco A. Servedio

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

2023

Testing Junta Truncation.

William He, Shivam Nadimpalli

CoRR, 2023

Testing Convex Truncation.

Anindya De, Shivam Nadimpalli, Rocco A. Servedio

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Testing and Learning Quantum Juntas Nearly Optimally.

Thomas Chen, Shivam Nadimpalli, Henry Yuen

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

2022

Approximating Sumset Size.

Anindya De, Shivam Nadimpalli, Rocco A. Servedio

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Convex Influences.

Anindya De, Shivam Nadimpalli, Rocco A. Servedio

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

2021

Quantitative Correlation Inequalities via Semigroup Interpolation.

Anindya De, Shivam Nadimpalli, Rocco A. Servedio

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021