{"ID":2844227,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.06171","arxiv_id":"2511.06171","title":"Halfspaces are hard to test with relative error","abstract":"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 from a target function $f: \\{0,1\\}^n \\to \\{0,1\\}$ that is being tested to a function $g$ is defined relative to the number of inputs $x$ for which $f(x)=1$; moreover, testing algorithms in this model have access both to a black-box oracle for $f$ and to independent uniform satisfying assignments of $f$. The motivation for this model is that it provides a natural framework for testing \\emph{sparse} Boolean functions that have few satisfying assignments, analogous to well-studied models for property testing of sparse graphs. The main result of this paper is a lower bound for testing \\emph{halfspaces} (i.e., linear threshold functions) in the relative error model: we show that $\\tildeΩ(\\log n)$ oracle calls are required for any relative-error halfspace testing algorithm over the Boolean hypercube $\\{0,1\\}^n$. This stands in sharp contrast both with the constant-query testability (independent of $n$) of halfspaces in the standard model [MORS10], and with the positive results for relative-error testing of many other classes given in [DHLNSY25, CPPS25a, CPPS25b]. Our lower bound for halfspaces gives the first example of a well-studied class of functions for which relative-error testing is provably more difficult than standard-model testing.","short_abstract":"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 from a target function $f: \\{0,1\\}^n \\to \\{0,1\\}$ that is being tested to a function $g$ is defined relative to the number of inputs $x$ fo...","url_abs":"https://arxiv.org/abs/2511.06171","url_pdf":"https://arxiv.org/pdf/2511.06171v2","authors":"[\"Xi Chen\",\"Anindya De\",\"Yizhi Huang\",\"Shivam Nadimpalli\",\"Rocco A. Servedio\",\"Tianqi Yang\"]","published":"2025-11-09T00:51:16Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.DS\"]","methods":"[]","has_code":false}