Relative-Error Testing of Conjunctions and Decision Lists

As our main results, we show that both classes of conjunctions and decision lists are efficiently testable in the relative-error model; indeed we give relative-error testing algorithms that have the same query complexity as the best standard-model testing algorithms.

For conjunctions we prove the following theorem:

Readers who are familiar with the literature on testing conjunctions in the standard setting may have noticed that the algorithm above is one-sided and uses $O(1/\epsilon )$ queries, while only two-sided algorithms are known for testing conjunctions in the standard model with $O(1/\epsilon )$ queries [35] and the current best one-sided algorithm needs $\tilde{O}(1/\epsilon )$ queries [27]. It was posed as an open problem in [4] whether there exists a one-sided, $O(1/\epsilon )$-query tester for conjunctions in the standard model. We resolve this question by giving such a tester as a corollary of Theorem 1:

Note that combining the first part of Equation 1 and Theorem 1 will only lead to a one-sided upper bound of $O(1/{\epsilon }^2)$ for the standard model, where the extra $1/\epsilon$ factor comes from the natural fact that whenever $f$ has density at least $\epsilon$, it takes $1/\epsilon$ uniformly random samples to simulate one sample from $f^{-1}(1)$. To prove Theorem 2, we obtain a more efficient reduction from relative-error testing to standard testing which, informally, states

from which Theorem 2 follows. The reduction is presented in Section 2.3.

Our second, and more involved, main result obtains an efficient relative-error testing algorithm for decision lists:

We remark that the algorithm of Theorem 3 crucially uses the relative-error testing algorithm for conjunctions, i.e. Theorem 1, as a subroutine; this is explained more below and a more detailed overview of the algorithm can be found in Section 4.2.

We also note that the algorithm of Theorem 3 is adaptive. However, an easy variant of our algorithm and analysis yields a non-adaptive $\epsilon$-relative-error tester for decision lists that makes $O(1/\epsilon )$ calls to $\mathrm{Samp}(f)$ and $\tilde{O}(1/{\epsilon }^2)$ calls to $\mathrm{MQ}(f)$ (see the full version).

Finally, we give a lower bound of $\mathrm{\Omega }(1/\epsilon )$ for any two-sided, adaptive algorithm for the relative-error testing of both conjunctions and decision lists, thus showing that Theorem 1 is optimal and Theorem 3 is nearly optimal (see the full version).

We give a brief and high-level overview of our techniques, referring the reader to Section 3.2 and Section 4.2 for more details. Our relative-error testing algorithm for conjunctions begins with a simple reduction to the problem of relative-error testing whether an unknown $f$ is an anti-monotone conjunction ⁵⁵5A conjunction is an anti-monotone conjunction if it only contains negated literals.. We solve the relative-error anti-monotone conjunction testing problem with an algorithm which, roughly speaking, first checks whether $f^{-1}(1)$ is close to a linear subspace (as would be the case if $f$ were an anti-monotone conjunction), and then checks whether $f$ is close to anti-monotone (in a suitable sense to meet our requirements). This is similar, at a high level, to the approach from [35], but as discussed in Section 3.2 there are various technical differences; in particular we are able to give a simpler analysis, even for the more general relative-error setting, which achieves one-sided rather than two-sided error.

For decision lists, our starting point is the simple observation that when $f$ is a sparse decision list then $f$ can be written as $C\wedge L$ where $C$ is a conjunction and $L$ is a decision list (intuitively, since $f$ is sparse, a large prefix of the list of output bits of the decision list must all be 0, which corresponds to a conjunction $C$); this decomposition plays an important role for us. Another simple but useful observation is that all of the variables in the conjunction $C$ must be “unanimous,” in the sense that each one of them must always take the same value across all of the positive examples. Our algorithm draws an initial sample of positive examples from $\mathrm{Samp}(f)$ and then works with a restriction of $f$ which fixes the variables which were seen to be “unanimous” in that initial sample. Intuitively, if $f$ is a decision list, then it should be the case that the resulting restricted function is close to a non-sparse decision list, so we can check that the restricted function is non-sparse, and, if the check passes, apply a standard-model decision list tester to the restricted function.

This gives some intuition for how to design an algorithm that accepts in the yes-case, but the fact that we must reject all functions that are relative-error far from decision lists leads to significant additional complications. To deal with this, we need to incorporate additional checks into the test, and we give an analysis showing that if a function $f$ passes all of these checks then it must be close (in a relative-error sense) to a function of the form $C^{\prime }\wedge L^{\prime }$ where $C^{\prime }$ is relative-error close to a conjunction and $L^{\prime }$ is relative-error close to a decision list; this lets us conclude that $f$ is relative-error close to a decision list, as desired. These checks involve applying our relative-error conjunction testing algorithm (which we show to have useful robustness properties against being run with a slightly imperfect sampling oracle – this robustness is crucial for our analysis); we refer the reader to Section 4.2 for more details.

Looking ahead, while our results resolve the relative-error testability of conjunctions and decision lists, there are many open questions remaining about how relative-error testing compares against standard-error testing for other natural and well-studied Boolean function classes, such as $s$-term DNF formulas, $k$-juntas, subclasses of $k$-juntas, unate functions, and beyond. All of these classes have been intensively studied in the standard testing model, see e.g. [19, 9, 31, 8, 32, 15, 16, 17, 15, 4]; it is an interesting direction for future work to establish either efficient relative-error testing algorithms, or relative-error testing lower bounds, for these classes.

Section 2 contains preliminary notation and definitions, and the general reduction from relative-error testing to standard testing is presented in Section 2.3. We give an outline of the proof of Theorem 1 in Section 3, and likewise for Theorem 3 in Section 4. Because of space constraints full proofs are deferred to the full version in the appendix.

Assume for a contradiction that $\mathrm{rel}\text{-}\mathrm{dist}(f,g)\le \epsilon /p_f$ for some $g\in 𝒞$. Then we have that:

which implies that $|f^{-1}(1)\mathrm{△}{g}^{-1}(1)|\le \epsilon 2^n$ and thus, $\mathrm{dist}(f,g)\le \epsilon$, a contradiction. $◀$

We now prove Lemma 8.

Our goal will be to show that Algorithm 1 is a standard testing algorithm for $𝒞$. Without loss of generality, we assume that $𝒜$ is correct with high enough probability, that is, if $\mathrm{rel}\text{-}\mathrm{dist}(f,𝒞)\ge \epsilon$ the algorithm rejects with probability at least $0.9$. Similarly, if $f\in 𝒞$, we assume that $𝒜$ accepts with probability at least $0.9$.

First, consider the case where $f\in 𝒞$. Note that $f$ can only be rejected if $𝒜$ rejects $f$. Since $𝑮$ is a set of uniformly random samples from $f^{-1}(1)$, $𝒜$ must accept with probability at least $0.9$. And if $𝒜$ is one-sided, then $f$ is always accepted, meaning that Algorithm 1 is also one-sided.

Now, assume that $f$ is $\epsilon$-far from any function in $𝒞$. Because the all-$0$ function is in $𝒞$ we must have $p_f:=|f^{-1}(1)|/2^n\ge \epsilon$. So on line 2, we have by a Chernoff bound that

by picking a suitably large constant $c_1$. Below we assume that $\widehat{𝒑}\in (1\pm 0.05)p_f$.

Since $p_f\ge \epsilon$, this implies $\widehat{𝒑}\ge \epsilon /2$. So, the algorithm doesn’t accept on line $3$. We also have that ${\mathrm{𝐏𝐫}}_{𝒛\sim {𝒰}_n}[f(𝒛)=1]\ge 0.9\widehat{𝒑}$. Hence, the expected size of $|𝑮|$ is at least $0.9c_2\widehat{𝒑}\cdot q(\epsilon /2,n)$. By our assumption on $q(\cdot ,\cdot )$ this is at least $0.9c_2\cdot q(\epsilon /2\widehat{p},n)$. Again, by a Chernoff bound and by picking $c_2$ to be a sufficiently large constant, we have that $|𝑮|\le q(\epsilon /2\widehat{𝒑},n)$ with probability at most $0.05$.

It remains to argue that $𝒜$ rejects with high probability on line $6$. By Lemma 9, we have that $\mathrm{rel}\text{-}\mathrm{dist}(f,𝒞)\ge \epsilon /p_f$. Using $\widehat{𝒑}\ge 0.95p_f$, we have that $\mathrm{rel}\text{-}\mathrm{dist}(f,𝒞)\ge \epsilon /2\widehat{𝒑}$. Since we simulate $𝒜$ on line $6$ using uniform samples from $f^{-1}(1)$, it must accept $f$ with probability at most $0.1$. As a result, the probability the algorithm accepts $f$ is at most $0.05+0.05+0.1\le 0.2$.

Line 2 uses $O(1/\epsilon )$ many queries, line 4 uses $O(q(\epsilon /2,n))$ many queries, and simulating $𝒜$ on line 6 uses $q(\epsilon /2\widehat{𝒑},n)=O(q(\epsilon /2,n))$ queries. So, the overall query complexity is $O(1/\epsilon +q(\epsilon /2,n))$. $◀$

Using the above, we can obtain a one-sided tester for conjunctions in the standard setting from our one-sided relative-error conjunction tester. The result of [5] implies an $\mathrm{\Omega }(1/\epsilon )$ lower bound for this problem, hence this result is tight.

Our relative-error tester for conjunctions in Theorem 1 makes $O(1/\epsilon )$ calls to $\mathrm{Samp}(f)$ and $\mathrm{MQ}(f)$ and is one-sided. As the all-$0$ function is a conjunction, the theorem follows by Lemma 8. $◀$

The “if” direction follows immediately from the following easy result of [35]:

For the other direction, suppose that $f(x)=x_{i_1}\wedge \mathrm{\cdots }\wedge x_{i_k}$ is an anti-monotone conjunction. Then clearly $f^{-1}(1)$ is an anti-monotone set. Moreover, for $x,y\in f^{-1}(1)$, $f(x\oplus y)=\neg (x_{i_1}\oplus y_{i_1})\wedge \mathrm{\dots }\wedge \neg (x_{i_k}\oplus y_{i_k})$. Since $x,y$ are both in $f^{-1}(1)$, $x_{i_1},\mathrm{\dots },x_{i_k},y_{i_1},\mathrm{\dots },y_{i_k}$ are all zero, and thus $f(x\oplus y)=1$. Recalling Definition 11, we have that $f^{-1}(1)$ is a linear subspace, so the only-if direction also holds. $◀$

Recall that Conj-Test first samples $𝒚\sim F$ and then runs Algorithm 2 on $f_{𝒚}$. When $f$ is a conjunction, $f_{𝒚}$ is an anti-monotone conjunction and thus, by Theorem 16 Conj-Test accepts with probability $1$. When $f$ is far from any conjunction, $f_{𝒚}$ must be far from any anti-monotone conjunction. So by Theorem 17, Conj-Test rejects with probability at least $0.9$. $◀$

Using the decomposition $f=C\wedge L$, we have

Given that the LHS is exactly half of the size of the set on the RHS, the first part follows.

Furthermore, consider any $i_j$ with . Exactly half of the strings $z$ in the set on the LHS of Equation 3 have $z_{i_j}=1$ and exactly half of them have $z_{i_j}=0$. Thus, we have for any $b\in \{0,1\}$,

where the last inequality used the second inclusion of Equation 3. This finishes the proof. $◀$

Let $f$ be a decision list represented by $(x_{i_1},b_1,v_1),\mathrm{\dots },$ $(x_{i_k},b_k,v_k),v_{\text{default}}$. Let $p$ be the pivot and $f=C\wedge L$ be the decomposition, where $C$ is a conjunction over variables in ${\mathscr{H}}_C:=\{i_1,\mathrm{\dots },i_{p-1}\}$ and $L$ is a decision list formed by the pivot and the tail of the list.

The first step of Algorithm 3 of the full paper draws samples from $\mathrm{Samp}(f)$ to partition variables into $𝑼\cup 𝑹$:

Now, the pivot variable $x_{i_p}$ can go either way, since it may be highly biased towards $b_p$. However, if it is too biased towards $b_p$ so that none of the samples $𝒛$ in $𝑺$ have ${𝒛}_p=1-b_p$, then one can argue that $f$ must be very close to a conjunction over ${\{0,1\}}^n$ in relative distance. Because of this, Step $0$ of Algorithm 3 of the full paper (which consists in running Conj-Test on $f$ with distance $\epsilon$) will accept $f$ with high probability.

Proceeding to Step 2, assume without loss of generality that Algorithm 3 of the full paper has found $𝑼$ and $𝑹$ such that ${\mathscr{H}}_C\subseteq 𝑼$ and $𝑹$ contains variables in the beginning part of $L$, including $i_p$, and the string $𝒖\in {\{0,1\}}^{𝑼}$ satisfies ${𝒖}_{i_j}=1-b_j$ for all $i_j\in {\mathscr{H}}_C$. This implies the following properties:

1. 1.

   The function $f{\upharpoonleft }_{𝒖}$ over ${\{0,1\}}^{𝑹}$ is a “dense” decision list, where “dense” means the number
   of its satisfying assignments is at least half of $2^{|𝑹|}$, and it is a decision list because the restriction of any decision list remains a decision list.

2. 2.

   For any $\alpha \in {\{0,1\}}^{𝑼}$, $f{\upharpoonleft }_{\alpha }$ is either the all-$0$ function (because $\alpha$ does not satisfy the conjunction $C$), or very close to $f{\upharpoonleft }_{𝒖}$ (because $𝑹$ contains the beginning part of the tail) and thus, both $f{\upharpoonleft }_{𝒖}$ and $f{\upharpoonleft }_{\alpha }$ are close to $L$ (when viewed as a decision list over $𝑹$) under the uniform distribution.

Given these properties of $𝑼,𝑹$ and $𝒖$, it is easy to see that $f$ passes both tests in Step 2 with high probability:

For step $4$, let $𝚪:{\{0,1\}}^{𝑼}\to \{0,1\}$ be defined as follows:

Now, observe that for any $\alpha \in {\{0,1\}}^{𝑼}$, either $\alpha$ does not satisfy $C$, in which case $f{\upharpoonleft }_{\alpha }$ is the all-$0$ function, or $\alpha$ satisfies $C$, in which case $f{\upharpoonleft }_{\alpha }$ is close to $f{\upharpoonleft }_{𝒖}$ and thus $\mathrm{\Gamma }(\alpha )=1$ (because $f{\upharpoonleft }_{𝒖}$ is “dense”). As a result, $𝚪$ is indeed the same as $C$ and thus it is a conjunction over ${\{0,1\}}^{𝑼}$. From this, it may seem straightforward to conclude that $\mathrm{\Gamma }$ always passes the test in Step 4 below:

Let’s now switch to the case when $f$ is $\epsilon$-far from any decision list in relative distance. Because conjunctions are special cases of decision lists, Step 0 (which consists in running Conj-Test on $f$) does not accept $f$ with high probability and Algorithm 3 of the full paper goes through Step 1 to obtain $𝑼,𝑹$ and $𝒖\in {\{0,1\}}^{𝑼}$. Let’s consider what conditions $f$ needs to satisfy in order for it to pass tests in Steps 2 and 3 with high probability:

1. 1.

   To pass Step 2, $f{\upharpoonleft }_{𝒖}$ over ${\{0,1\}}^{𝑹}$ needs to be “dense:” $|f\upharpoonleft _{𝒖}^{}{}_{}{}^{(-1)}(1)|\ge 2^{|𝑹|}/8$, and must also be $(\epsilon /100)$-close to a decision list under the uniform distribution.

2. 2.

   To understand the necessary condition posed on $f$ to pass Step 3, let’s introduce the following function $𝒈:{\{0,1\}}^n\to \{0,1\}$, which is closely related to $𝚪$ defined earlier and
   will play a crucial role in the analysis:

   $$𝒈(x)=𝚪(x_{𝑼})\wedge f(𝒖\circ x_{𝑹}).$$

   We show that to pass Step 3 with high probability, it must be the case that $\mathrm{rel}\text{-}\mathrm{dist}(f,𝒈)$ is small. This means that for each $\alpha \in {\{0,1\}}^{𝑼}$, one can replace $f{\upharpoonleft }_{\alpha }$ by the all-$0$ function if $𝚪(\alpha )=0$ (which means that $f{\upharpoonleft }_{\alpha }$ is not dense enough), and replace $f{\upharpoonleft }_{\alpha }$ by $f{\upharpoonleft }_{𝒖}$ otherwise, and this will only change a small number of bits of $f$ (relative to $|f^{-1}(1)|$). Note that $𝒈$ is getting closer to the decomposition of a decision list since we know $f{\upharpoonleft }_{𝒖}$ is close to a decision list over ${\{0,1\}}^{𝑹}$.

Assuming all the necessary conditions summarized above for $f$ to pass Steps 2 and 3 and using the assumption that $f$ is far from decision lists in relative distance, we show that $𝚪$ must be far from conjunctions in relative distance. Finally, given the latter, it can be shown that Conj-Test in Step 4 rejects with high probability, again by analyzing performance guarantees of Algorithm 5 of the full paper and Algorithm 4 of the full paper as simulators of sampling and query oracles of $𝚪$, respectively, so that Theorem 19 for Conj-Test can be applied.