Shivam Nadimpalli

43 papers A* 13A 4Journal 25

Year	Rank	Type	Title / Venue / Authors
2026	A*	`conf`	Halfspaces are hard to test with relative error. SODA Xi Chen, Anindya De, Yizhi Huang, Shivam Nadimpalli, Rocco A. Servedio, Tianqi Yang
2025	A*	`conf`	DNF Learning via Locally Mixing Random Walks. STOC Josh Alman, Shivam Nadimpalli, Shyamal Patel, Rocco A. Servedio
2025	J	`jnl`	DNF Learning via Locally Mixing Random Walks. CoRR Josh Alman, Shivam Nadimpalli, Shyamal Patel, Rocco A. Servedio
2025	A*	`conf`	Faster Exact Learning of k-Term DNFs with Membership and Equivalence Queries. FOCS Josh Alman, Shivam Nadimpalli, Shyamal Patel, Rocco A. Servedio
2025	J	`jnl`	Faster exact learning of k-term DNFs with membership and equivalence queries. CoRR Josh Alman, Shivam Nadimpalli, Shyamal Patel, Rocco A. Servedio
2025	J	`jnl`	Halfspaces are hard to test with relative error. CoRR Xi Chen, Anindya De, Yizhi Huang, Shivam Nadimpalli, Rocco A. Servedio, Tianqi Yang
2025	J	`jnl`	Learning and Testing Convex Functions. CoRR Renato Ferreira Pinto Jr., Cassandra Marcussen, Elchanan Mossel, Shivam Nadimpalli
2025	A*	`conf`	Lower Bounds for Convexity Testing. SODA Xi Chen, Anindya De, Shivam Nadimpalli, Rocco A. Servedio, Erik Waingarten
2025	J	`jnl`	Model-agnostic super-resolution in high dimensions. CoRR Xi Chen, Anindya De, Yizhi Huang, Shivam Nadimpalli, Rocco A. Servedio, Tianqi Yang
2025	J	`jnl`	No Price Tags? No Problem: Query Strategies for Unpriced Information. CoRR Shivam Nadimpalli, Mingda Qiao, Ronitt Rubinfeld
2025	A*	`conf`	Relative-error monotonicity testing. SODA Xi Chen, Anindya De, Yizhi Huang, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio, Tianqi Yang
2025	A	`conf`	Testing Sumsets Is Hard. ESA Xi Chen, Shivam Nadimpalli, Tim Randolph, Rocco A. Servedio, Or Zamir
2025	J	`jnl`	Testing noisy low-degree polynomials for sparsity. CoRR Yiqiao Bao, Anindya De, Shivam Nadimpalli, Rocco A. Servedio, Nathan White
2024	—	`—`	A Complexity-Theoretic Perspective on Convex Geometry Shivam Nadimpalli
2024	J	`jnl`	A Counterexample to a Directed KKL Inequality. Electron. J. Comb. Quentin Dubroff, Shivam Nadimpalli, Bhargav Narayanan
2024	A*	`conf`	Detecting Low-Degree Truncation. STOC Anindya De, Huan Li, Shivam Nadimpalli, Rocco A. Servedio
2024	J	`jnl`	Detecting Low-Degree Truncation. CoRR Anindya De, Huan Li, Shivam Nadimpalli, Rocco A. Servedio
2024	A*	`conf`	Gaussian Approximation of Convex Sets by Intersections of Halfspaces. FOCS Anindya De, Shivam Nadimpalli, Rocco A. Servedio
2024	J	`jnl`	Lower Bounds for Convexity Testing. CoRR Xi Chen, Anindya De, Shivam Nadimpalli, Rocco A. Servedio, Erik Waingarten
2024	A*	`conf`	Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas. SODA Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio
2024	A*	`conf`	On the Pauli Spectrum of QAC0. STOC Shivam Nadimpalli, Natalie Parham, Francisca Vasconcelos, Henry Yuen
2024	J	`jnl`	Optimal Non-Adaptive Tolerant Junta Testing via Local Estimators. CoRR Shivam Nadimpalli, Shyamal Patel
2024	A*	`conf`	Optimal Non-adaptive Tolerant Junta Testing via Local Estimators. STOC Shivam Nadimpalli, Shyamal Patel
2024	J	`jnl`	Relative-error monotonicity testing. CoRR Xi Chen, Anindya De, Yizhi Huang, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio, Tianqi Yang
2024	J	`jnl`	Sparsifying Suprema of Gaussian Processes. CoRR Anindya De, Shivam Nadimpalli, Ryan O'Donnell, Rocco A. Servedio
2024	A	`conf`	Testing Intersecting and Union-Closed Families. ITCS Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio
2024	J	`jnl`	Testing Sumsets is Hard. CoRR Xi Chen, Shivam Nadimpalli, Tim Randolph, Rocco A. Servedio, Or Zamir
2023	J	`jnl`	Gaussian Approximation of Convex Sets by Intersections of Halfspaces. CoRR Anindya De, Shivam Nadimpalli, Rocco A. Servedio
2023	J	`jnl`	Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas. CoRR Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio
2023	J	`jnl`	On the Pauli Spectrum of QAC0. CoRR Shivam Nadimpalli, Natalie Parham, Francisca Vasconcelos, Henry Yuen
2023	A*	`conf`	Testing Convex Truncation. SODA Anindya De, Shivam Nadimpalli, Rocco A. Servedio
2023	J	`jnl`	Testing Convex Truncation. CoRR Anindya De, Shivam Nadimpalli, Rocco A. Servedio
2023	J	`jnl`	Testing Intersecting and Union-Closed Families. CoRR Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio
2023	J	`jnl`	Testing Junta Truncation. CoRR William He, Shivam Nadimpalli
2023	A*	`conf`	Testing and Learning Quantum Juntas Nearly Optimally. SODA Thomas Chen, Shivam Nadimpalli, Henry Yuen
2022	J	`jnl`	A Counterexample to a Directed KKL Inequality. CoRR Quentin Dubroff, Shivam Nadimpalli, Bhargav Narayanan
2022	A*	`conf`	Approximating Sumset Size. SODA Anindya De, Shivam Nadimpalli, Rocco A. Servedio
2022	A	`conf`	Convex Influences. ITCS Anindya De, Shivam Nadimpalli, Rocco A. Servedio
2022	J	`jnl`	Testing and Learning Quantum Juntas Nearly Optimally. CoRR Thomas Chen, Shivam Nadimpalli, Henry Yuen
2021	J	`jnl`	Approximating Sumset Size. CoRR Anindya De, Shivam Nadimpalli, Rocco A. Servedio
2021	J	`jnl`	Convex Influences. CoRR Anindya De, Shivam Nadimpalli, Rocco A. Servedio
2021	A	`conf`	Quantitative Correlation Inequalities via Semigroup Interpolation. ITCS Anindya De, Shivam Nadimpalli, Rocco A. Servedio
2020	J	`jnl`	Quantitative Correlation Inequalities via Semigroup Interpolation. CoRR Anindya De, Shivam Nadimpalli, Rocco A. Servedio