7 papers
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…
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…
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…
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…