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