10 citations · 10 across the 21 of their papers we have counts for
6 papers · 1 filter
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…