13 papers
Distribution-Free Halfspace Testing with Samples
Xi Chen, Renato Ferreira Pinto, Nathaniel Harms +2
We prove a tight lower bound on the number of samples required for testing halfspaces over , in the distribution-free sample-based model where the underlying…
Model-agnostic super-resolution in high dimensions
Xi Chen, Anindya De, Yizhi Huang +3
The problem of super-resolution, roughly speaking, is to reconstruct an unknown signal to high accuracy, given (potentially noisy) information about its low-degree Fourier coeffici…
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…
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…
DNF formulas are efficiently testable with relative error
Xi Chen, William Pires, Toniann Pitassi +1
We give a poly-query algorithm for testing whether an unknown and arbitrary function is an -term DNF, in the challenging relative-error fram…
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…