Several recent works \cite{CDHLNSY25,CPPS25conjunctionDL,CPPS25junta,rel-error-DNF} have studied a model of property testing of Boolean functions under a 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 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{\Omega}(\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 \cite{MORS10}, and with the positive results for relative-error testing of many other classes given in \cite{CDHLNSY25,CPPS25conjunctionDL,CPPS25junta,rel-error-DNF}. 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.