9 papers · 1 filter
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…
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…
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…