From the 1 of 15 linked papers with an AI index.
15 papers
Learning and Testing Convex Functions
Renato Ferreira Pinto, Cassandra Marcussen, Elchanan Mossel +1
The paper investigates how to learn and test real-valued convex functions under the Gaussian distribution, providing algorithms with explicit sample‑complexity bounds assuming the…
Testing Unate Distributions
Daeho Lee, Shivam Nadimpalli, Mingda Qiao +1
We initiate the study of *unate distributions* over -- a natural analogue of unate Boolean functions -- by considering two basic testing problems that parallel well-st…
Optimal Sparsification of Gaussian Processes
Shivam Nadimpalli
We prove an optimal dimension-free sparsification theorem for suprema of centered Gaussian processes. Given a bounded set , we show that the supremum of the…
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…