1 citations · 1 across the 10 of their papers we have counts for
13 papers
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…
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…
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…
Trace reconstruction from local statistical queries
Xi Chen, Anindya De, Chin Ho Lee +1
The goal of trace reconstruction is to reconstruct an unknown -bit string given only independent random traces of , where a random trace of is obtained by passing …
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…
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…
Efficient deterministic approximate counting for low-degree polynomial threshold functions
Anindya De, Rocco Servedio
We give a deterministic algorithm for approximately counting satisfying assignments of a degree- polynomial threshold function (PTF). Given a degree- input polynomial $p(x_1,…