Sublinear-query relative-error testing of halfspaces

View PDF

Abstract: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 a small fraction of all input assignments satisfy the function. In this framework, the distance from the unknown target function $f$ that is being tested to a function $g$ is defined as $\mathrm{Vol}(f \mathop{\triangle} g)/\mathrm{Vol}(f)$, where the numerator is the fraction of inputs on which $f$ and $g$ disagree and the denominator is the fraction of inputs that satisfy $f$. Recent work [CDHNSY26] has shown that over the Boolean domain ${0,1}^n$, any relative-error testing algorithm for the fundamental class of halfspaces (i.e. linear threshold functions) must make $\Omega(\log n)$ oracle calls. In this paper we complement the [CDHNSY26] lower bound by showing that halfspaces can be relative-error tested over $\mathbb{R}^n$ under the standard $N(0,I_n)$ Gaussian distribution using a sublinear number of oracle calls -- in particular, substantially fewer than would be required for learning. Our results use a wide range of tools including Hermite analysis, Gaussian isoperimetric inequalities, and geometric results on noise sensitivity and surface area.

Subjects:

Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)

Cite as: arXiv:2604.01557 [cs.DS]

(or arXiv:2604.01557v1 [cs.DS] for this version)

https://doi.org/10.48550/arXiv.2604.01557

arXiv-issued DOI via DataCite (pending registration)

Submission history

From: Yizhi Huang [view email] [v1] Thu, 2 Apr 2026 03:01:25 UTC (197 KB)