Relative-Error Unateness Testing

Taken together, our positive and negative results give a fairly complete picture of the abilities and limitations of relative-error algorithms for testing unateness. It is interesting to compare our results for relative-error unateness testing with the known results for unateness testing in the standard model [5, 13, 12]. Recall that in the standard model, essentially tight upper and lower bounds are known both for one-sided non-adaptive algorithms ($\tilde{\mathrm{\Theta }}(n)$ queries) and for two-sided adaptive algorithms ($\tilde{\mathrm{\Theta }}(n^{2/3})$ queries). In contrast, in the relative-error setting we give essentially tight upper and lower bounds of $\tilde{\mathrm{\Theta }}(\log N)$ queries for one-sided non-adaptive algorithms (in fact our lower bound holds even for two-sided non-adaptive algorithms), but our upper bound for two-sided adaptive algorithms is $\tilde{O}(\log N)$ queries whereas our lower bound is $\tilde{\mathrm{\Omega }}({(\log N)}^{2/3})$ queries. Roughly speaking, the reason for this disparity with what can be proved in the standard model is as follows: The $\tilde{O}(n^{2/3})$-query standard-model unateness testing algorithm of [12] crucially employs a novel use of binary search over long random paths in the Boolean hypercube ${\{0,1\}}^n$. As demonstrated by our lower bound constructions, though, in the relative-error setting “all of the action” may take place over just two adjacent layers of the hypercube, which precludes an analysis using long paths in the hypercube. Thus, it is not clear how to use techniques inspired by [12] to obtain an improved algorithmic result in the relative-error setting. An interesting direction for future work is to close the gap left open by our results for adaptive relative-error unateness testing: is the right answer closer to ${(\log N)}^{2/3},$ or to $\log N$?

It is also interesting to consider our result for relative-error unateness testing in the context of the [6] results for relative-error monotonicity testing. In both cases, the query complexity of relative-error testing depends on the sparsity $N=|f^{-1}(1)|$ of the function being tested; as discussed earlier, this is provably different from what happens for other properties such as conjunctions, decision lists, and juntas [10, 11]. We note that those other properties are most naturally defined using a “syntactic” description of how the relevant functions can be represented in various models, while in contrast monotonicity and unateness are most naturally viewed as “semantic” properties which are defined in terms of the behavior of the function’s output values rather than in terms of a particular syntactic representation. An interesting possible direction for future research would be to study other “semantic” Boolean function properties: will it turn out that for them too, the complexity of relative-error testing is determined by the sparsity $N=|f^{-1}(1)|$? Some possible properties to investigate in this context are union-closedness and intersectingness, which have been studied in the standard property testing model in recent work [8, 16].

We present two unateness testers in the relative-error model. The first tester needs to be given the sparsity $N$ as an input, while the second does not. As a starting point, we first introduce two related procedures from prior work that our algorithms will build on. In each case, the brief description given below is a simplified version of the actual procedure given in the relevant paper.

1. 1.

   Relative-Error Monotonicity Testing, from [6]. This procedure repeatedly draws samples from the $\mathrm{Samp}(f)$ oracle. For each sample $𝒛\sim f^{-1}(1)$, it draws an index $𝒊$ uniformly from $\{i\in [n]\mid {𝒛}_i=0\}$, and queries $f(𝒛\oplus e_{𝒊})$. If the result is $0$, the procedure rejects. This test is one-sided, non-adaptive, and has query complexity $O(\log (N)/\epsilon )$; it is the inspiration for the BiasedTest subroutine in the full version of this paper [9].

2. 2.

   Standard-Model Unateness Testing, from [2]. The idea of this procedure is to find both a strictly monotone and a strictly anti-monotone edge along the same coordinate $i$, which directly witnesses a violation of unateness. The procedure can be thought of as interpolating between two extreme cases. First, when violations are concentrated entirely along one coordinate, we choose to sample many coordinates. However, for each coordinate that is sampled, we check only a few edges in that dimension. Second, when violations are spread equally across all coordinates, we choose to sample very few coordinates but for each chosen coordinate, we check more edges in that dimension. This test is one-sided, non-adaptive, and has query complexity $\tilde{O}(n/\epsilon )$; it is the inspiration for the UnbiasedTest subroutine in the full version of this paper [9].

Of course, if $n=O(\log N)$, then we could directly use the standard-model unateness tester. However, the interesting case for relative-error testing is when $n\gg \log N$. Recall that a function $f$ is unate if and only if it is monotone along some direction $d\in {\{0,1\}}^n$. To make use of the relative-error monotonicity tester, we would need to provide some direction $\tilde{d}$. Unfortunately, it is not clear how to choose a suitable direction $\tilde{d}$; indeed, if the relative-error monotonicity tester reports that the function $f$ is not monotone along some specific direction $\tilde{d}$, we cannot obviously conclude that $f$ is not unate – perhaps $f$ is unate by virtue of being monotone along some other direction $d\ne \tilde{d}.$ Ideally, we would like to identify a direction $\tilde{d}\in {\{0,1\}}^n$ such that if $f$ is unate, then (with high probability) it is monotone along direction $\tilde{d}$.

This goal is too optimistic because we cannot be confident in the setting of all $n$ coordinates. However, we can confidently set many coordinates of $\tilde{d}$, as we now explain. For any unate function $f$, if the value of the $i$-th coordinate of a uniform sample drawn from $f^{-1}(1)$ is $1$ (resp. $0$) with probability $p_i>0.5$, then $f$ must be monotone (resp. anti-monotone) along dimension $i$. This notion is formalized in Observation 9. Thus, a natural approach is to draw some samples from $f^{-1}(1)$, use them to obtain an estimate $\widehat{p_i}$ of the above probabilities $p_i$ for each coordinate $i\in [n]$, and choose directions for the subset of coordinates $i$ where $\widehat{p_i}$ is either close to 0 or close to 1 (see Phase 1 of the Unateness-Tester-Known-N algorithm in the full version). We call such coordinates fixed (since we fix the direction along these coordinates). For these fixed coordinates, if we see a bichromatic edge along a coordinate $i$ that “runs counter to $\widehat{p_i}$” (for example, an anti-monotone edge along a coordinate $i$ such that $\widehat{p_i}$ is close to 1), we can be “quite confident” that $f$ is not unate.

At a high level, the strategy of our algorithm is to run (a variant of) the relative-error monotonicity tester along the fixed coordinates and to run (a variant of) the standard-model unateness tester along the unfixed coordinates (see Phase 3 of the Unateness-Tester-Known-N algorithm in the full version [9]). Both testers are slightly modified to search for violations only on the coordinates provided.⁶⁶6This modification is easy, because both subroutines are edge-testers; we provide the relevant set of coordinates as input to the procedure, and we have the procedure only perform edge-tests along the coordinates provided in the input set.

For this to succeed, there are two technical challenges that must be overcome. First, in order to fix $n$ directions such that with constant probability we fix all of them correctly, $\mathrm{\Omega }(\log n)$ samples are required. For very sparse functions, such that $\log N=o(\log n)$, this is an unacceptably high number of samples. Second, our modified standard-model unateness tester has query complexity which is quasilinear in the number of unfixed coordinates. Thus, we must ensure that we fix all but $O(\log N)$ coordinates.

Our non-adaptive lower bound, Theorem 3, is obtained via a modification of the lower bound arguments from [6]. As in that work, our lower bound construction uses functions which are only nontrivial on two adjacent layers of the Boolean hypercube; we call these two-layer functions (see Section 7.1.1 in the full version [9]). More precisely, a function $f$ is a two-layer function if it is only nontrivial on points in layers $3n/4$ and $3n/4+1$: every point with weight is set to $0$ and every point with weight $>3n/4+1$ is set to $1$. (We use the constant $3/4$ just to make the presentation more concrete; it can be replaced by any constant strictly between $1/2$ and $1$).

Our “yes-functions” are the same as the “yes-functions” of [6], which are monotone (and hence unate) functions. However, we modify the “no-functions” of [6] since the analysis of [6] does not establish that the “no-functions” that were used in that work, to give lower bounds on relative-error monotonicity testing, are far from unate. In Section 7 of the full version we give a detailed description of a new distribution of “no-functions” and prove that they are indeed suitably far from unate. Given these no-functions, our lower bounds follow from relatively simple modifications of the [6] lower bound arguments; we describe the necessary modifications in Section 7 of the full version.

Our adaptive lower bound (Theorem 4) is obtained by a simple reduction to the $\tilde{\mathrm{\Omega }}(d^{2/3})$-query standard-model two-sided adaptive unateness testing lower bound given by [13] for functions $f:{\{0,1\}}^d\to \{0,1\}$. This is done by “scaling down” both the yes- and no- distributions used in that lower bound so that the functions involved are contained in a subcube of ${\{0,1\}}^n$ of dimension $d\approx \log N$; this can be done by simply defining the functions over ${\{0,1\}}^n$ to output 0 if any of the last $n-d$ input coordinates take value 1. For such functions, the uniform random satisfying assignments that a relative-error testing algorithm may ask for can easily be obtained by a standard-model algorithm for unateness testing over ${\{0,1\}}^d$, by simply drawing uniform random assignments from ${\{0,1\}}^d\circ 0^{n-d}$ until a satisfying assignment is received. It follows that the $\tilde{\mathrm{\Omega }}(d^{2/3})$ standard-model lower bound of [13] directly yields a $\tilde{\mathrm{\Omega }}({(\log N)}^{2/3})$ lower bound for two-sided adaptive unateness testing with relative error. (We mention that it is easily verified that in the [13] construction, for both the distribution ${𝒟}_{\mathrm{yes}}$ of yes-functions and the distribution ${𝒟}_{\mathrm{no}}$ of no-functions, with very high probability the number of satisfying assignments of a random function drawn from either distribution is tightly concentrated around the same particular value. This is why the lower bound of Theorem 4 holds even when $N$ is given to the testing algorithm.)

We remark that an alternate route to obtaining a $\tilde{\mathrm{\Omega }}({(\log N)}^{2/3})$-query two-sided adaptive lower bound for relative-error unateness testing is to proceed in analogy with our proof of Theorem 3, i.e. to modify the “no-functions” used in the two-sided adaptive lower bound for relative-error monotonicity testing of [6]. Given suitably modified “no-functions” that are far from unate in relative error, the $\tilde{\mathrm{\Omega }}({(\log N)}^{2/3})$ lower bound argument of [6] for monotonicity adapts to give a $\tilde{\mathrm{\Omega }}({(\log N)}^{2/3})$ lower bound for two-sided adaptive relative-error unateness testing, matching the parameters of Theorem 4. Since this construction and argument have many more details than the simple reduction sketched in the previous paragraph, though, we omit them.

For $i\in [n]$, we say a function $f:{\{0,1\}}^n\to \{0,1\}$ is $1$-monotone in the $i$-th direction if every $\{x^{i\leftarrow 0},x^{i\leftarrow 1}\}\in {\text{Edge}}_i$ satisfies $f(x^{i\leftarrow 0})\le f(x^{i\leftarrow 1})$. Similarly, we say a function $f$ is $0$-monotone in the $i$-th direction if every $\{x^{i\leftarrow 0},x^{i\leftarrow 1}\}\in {\text{Edge}}_i$ satisfies $f(x^{i\leftarrow 0})\ge f(x^{i\leftarrow 1})$. We say $f$ is unate if it is either $1$-monotone or $0$-monotone in the $i$-th direction for every $i\in [n]$.

The following is an immediate consequence of the definition of $d^f$:

We also have the following useful lemma, whose proof can be found in the full version [9], which roughly shows that it is easy to find a bichromatic edge in a biased direction given a uniformly random preimage of $f^{-1}(1)$:

Our algorithms will reject if they find an $i\in [n]$ along with a pair of edges $e\in {\text{Edge}}_i^0(f)$ and $e^{\prime }\in {\text{Edge}}_i^1(f)$. It is easy to see that when $f$ is unate, this can never happen:

We will need the following theorem which relates the distance to unateness and the number of edges violating $b$-monotonicity:

Recalling that $N=f^{-1}(1)$, where $f$ is the function being tested for unateness we have:

We will also use the following simple lemma, which shows that if $f$ is unate then the distance between any two points in $f^{-1}(1)$ is at most $O(\log N)$:

Given a positive integer $r$ and $\tilde{d}\in {\{0,1,\ast \}}^n$, we say a function $h:{\{0,1\}}^n\to \{0,1\}$ is $(r,\tilde{d})$-truncated if every $x\in h^{-1}(1)$ satisfies $\mathrm{\Delta }(x,\tilde{d})\le r$.

Given $r$ and $\tilde{d}$, an $(r,\tilde{d})$-truncated function $h=f_{r,\tilde{d}}$ is naturally obtained from $f$, the function being tested, as follows:

The proof of the following lemma can be found in the full version [9].

We present a key lemma that is central to the analysis of our main algorithms. The lemma roughly states that given any function $h:{\{0,1\}}^n\to \{0,1\}$ that is far from unate (in $\mathrm{𝗋𝖾𝗅𝖽𝗂𝗌𝗍}$), there are many violations on at least one of two index sets which partition $[n]$.