2026-07-20T15:08:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26450 2026-07-01T07:16:11Z ddc:004 open_access

Sublinear-Query Relative-Error Testing of Halfspaces Chen, Xi De, Anindya Huang, Yizhi Nadimpalli, Shivam Servedio, Rocco A. Yang, Tianqi Property testing relative-error testing halfspaces Gaussian space The relative-error property testing model was introduced in [Chen et al., 2024] 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 Vol(f△g)/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 [Chen et al., 2026] has shown that over the Boolean domain {0,1}ⁿ, any relative-error testing algorithm for the fundamental class of {halfspaces} (i.e. linear threshold functions) must make Ω(log n) oracle calls. In this paper we complement the [Chen et al., 2026] lower bound by showing that halfspaces can be relative-error tested over ℝⁿ 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xi Chen and Anindya De and Yizhi Huang and Shivam Nadimpalli and Rocco A. Servedio and Tianqi Yang 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.61 urn:nbn:de:0030-drops-264508 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.61 eng https://creativecommons.org/licenses/by/4.0/legalcode