10 citations · 10 across the 21 of their papers we have counts for
28 papers
Testing Unate Distributions
Daeho Lee, Shivam Nadimpalli, Mingda Qiao +1
We initiate the study of *unate distributions* over -- a natural analogue of unate Boolean functions -- by considering two basic testing problems that parallel well-st…
Optimal Sparsification of Gaussian Processes
Shivam Nadimpalli
We prove an optimal dimension-free sparsification theorem for suprema of centered Gaussian processes. Given a bounded set , we show that the supremum of the…
Sublinear-query relative-error testing of halfspaces
Xi Chen, Anindya De, Yizhi Huang +3
The relative-error property testing model was introduced in [CDHLNSY24] to facilitate the study of property testing for "sparse" Boolean-valued functions, i.e. ones for which only…
Testing noisy low-degree polynomials for sparsity
Yiqiao Bao, Anindya De, Shivam Nadimpalli +2
We consider the problem of testing whether an unknown low-degree polynomial over is sparse versus far from sparse, given access to noisy evaluations of the polyn…
No Price Tags? No Problem: Query Strategies for Unpriced Information
Shivam Nadimpalli, Mingda Qiao, Ronitt Rubinfeld
The classic *priced query model*, introduced by Charikar et al. (STOC 2000), captures the task of computing a known function on an unknown input when each input variable can only b…
Learning and Testing Convex Functions
Renato Ferreira Pinto, Cassandra Marcussen, Elchanan Mossel +1
We consider the problems of \emph{learning} and \emph{testing} real-valued convex functions over Gaussian space. Despite the extensive study of function convexity across mathematic…
Model-agnostic distribution recovery in high dimension via Fourier measurements
Xi Chen, Anindya De, Yizhi Huang +3
We study the problem of reconstructing an unknown probability distribution to high accuracy, given noisy information about its low-degree Fourier coefficients. Prior results for th…
Halfspaces are hard to test with relative error
Xi Chen, Anindya De, Yizhi Huang +3
Several recent works [DHLNSY25, CPPS25a, CPPS25b] have studied a model of property testing of Boolean functions under a \emph{relative-error} criterion. In this model, the distance…
On the Maximal Gaussian Perimeter of Convex Sets, Revisited
Shivam Nadimpalli, Caleb Pascale
We revisit Nazarov's construction of a convex set with nearly maximal Gaussian surface area and give an alternate analysis based on the notion of convex influence.
Faster exact learning of k-term DNFs with membership and equivalence queries
Josh Alman, Shivam Nadimpalli, Shyamal Patel +1
In 1992 Blum and Rudich [BR92] gave an algorithm that uses membership and equivalence queries to learn -term DNF formulas over in time , improv…
DNF Learning via Locally Mixing Random Walks
Josh Alman, Shivam Nadimpalli, Shyamal Patel +1
We give two results on PAC learning DNF formulas using membership queries in the challenging "distribution-free" learning framework, where learning algorithms must succeed for an a…
Sparsifying Suprema of Gaussian Processes
Anindya De, Shivam Nadimpalli, Ryan O'Donnell +1
We give a dimension-independent sparsification result for suprema of centered Gaussian processes: Let be any (possibly infinite) bounded set of vectors in , and l…
Lower Bounds for Convexity Testing
Xi Chen, Anindya De, Shivam Nadimpalli +2
We consider the problem of testing whether an unknown and arbitrary set (given as a black-box membership oracle) is convex, versus -far from…
Relative-error monotonicity testing
Xi Chen, Anindya De, Yizhi Huang +4
The standard model of Boolean function property testing is not well suited for testing functions which have few satisfying assignments, since every such function…
Optimal Non-Adaptive Tolerant Junta Testing via Local Estimators
Shivam Nadimpalli, Shyamal Patel
We give a non-adaptive algorithm that makes queries to a Boolean function and d…
Testing Sumsets is Hard
Xi Chen, Shivam Nadimpalli, Tim Randolph +2
A subset of the Boolean hypercube is a sumset if for some . Sumsets are central objects of study in add…
Detecting Low-Degree Truncation
Anindya De, Huan Li, Shivam Nadimpalli +1
We consider the following basic, and very broad, statistical problem: Given a known high-dimensional distribution over and a collection of data points in…
Testing Intersecting and Union-Closed Families
Xi Chen, Anindya De, Yuhao Li +2
Inspired by the classic problem of Boolean function monotonicity testing, we investigate the testability of other well-studied properties of combinatorial finite set systems, speci…
Gaussian Approximation of Convex Sets by Intersections of Halfspaces
Anindya De, Shivam Nadimpalli, Rocco A. Servedio
We study the approximability of general convex sets in by intersections of halfspaces, where the approximation quality is measured with respect to the standard Gauss…
On the Pauli Spectrum of QAC0
Shivam Nadimpalli, Natalie Parham, Francisca Vasconcelos +1
The circuit class was introduced by Moore (1999) as a model for constant depth quantum circuits where the gate set includes many-qubit Toffoli gates. Proving lower…
Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas
Xi Chen, Anindya De, Yuhao Li +2
We give the first super-polynomial (in fact, mildly exponential) lower bounds for tolerant testing (equivalently, distance estimation) of monotonicity, unateness, and juntas with a…
Testing Junta Truncation
William He, Shivam Nadimpalli
We consider the basic statistical problem of detecting truncation of the uniform distribution on the Boolean hypercube by juntas. More concretely, we give upper and lower bounds on…
Testing Convex Truncation
Anindya De, Shivam Nadimpalli, Rocco A. Servedio
We study the basic statistical problem of testing whether normally distributed -dimensional data has been truncated, i.e. altered by only retaining points that lie in some unkno…
A Counterexample to a Directed KKL Inequality
Quentin Dubroff, Shivam Nadimpalli, Bhargav Narayanan
We show that the natural directed analogues of the KKL theorem [KKL88] and the Eldan--Gross inequality [EG20] from the analysis of Boolean functions fail to hold. This is in contra…