We study the \emph{relative-error} property testing model for Boolean functions that was recently introduced in the work of \cite{CDHLNSY2024}. In relative-error testing, the testing algorithm gets uniform random satisfying assignments as well as black-box queries to $f$, and it must accept $f$ with high probability whenever $f$ has the property that is being tested and reject any $f$ that is \emph{relative-error} far from having the property. Here the relative-error distance from $f$ to a function $g$ is measured with respect to $|f^{-1}(1)|$ rather than with respect to the entire domain size $2^n$ as in the Hamming distance measure that is used in the standard model; thus, unlike the standard model, relative-error testing allows us to study the testability of \emph{sparse} Boolean functions that have few satisfying assignments. It was shown in \cite{CDHLNSY2024} that relative-error testing is at least as difficult as standard-model property testing, but for many natural and important Boolean function classes the precise relationship between the two notions is unknown.
In this paper we consider the well-studied and fundamental properties of being a \emph{conjunction} and being a \emph{decision list}. In the relative-error setting, we give an efficient one-sided error tester for conjunctions with running time and query complexity $O(1/\epsilon)$.
Secondly, we give a two-sided relative-error $\tilde{O}(1/\epsilon)$ tester for decision lists, matching the query complexity of the state-of-the-art algorithm in the standard model \cite{Bshouty20,DLM+:07}.