Distribution-free Junta Testing Distribution-free Junta Testing

Our main positive result is a $\mathrm{poly}(k)/\epsilon$-query one-sided adaptive algorithm for distribution-free $k$-junta testing:

Theorem 1.1 shows that $k$-juntas stand in interesting contrast with many other well-studied classes of Boolean functions in property testing such as conjunctions, decision lists, linear threshold functions, and monotone functions. For each of these classes, distribution-free testing requires dramatically more queries than uniform-distribution testing: for the first three classes the separation is $\mathrm{poly}(1/\epsilon)$ queries in the uniform setting (Parnas et al. 2002; Matulef et al. 2010) versus $n^{\Omega (1)}$ queries in the distribution-free setting (Glasner and Servedio 2009; Chen and Xie 2016); for $n$-variable monotone functions $\mathrm{poly}(n)$ queries suffice in the uniform setting (Goldreich et al. 2000; Khot et al. 2015), whereas Halevy and Kushilevitz (2007) show that $2^{\Omega (n)}$ queries are required in the distribution-free setting. In contrast, Theorem 1.1 shows that for $k$-juntas the query complexities of uniform-distribution and distribution-free testing are polynomially related (indeed, within at most a quadratic factor of each other).

Complementing the strong upper bound that Theorem 1.1 gives for adaptive testers, our main negative result is an $\Omega (2^{k/3})$-query lower bound for non-adaptive testers:

Theorems 1.1 and 1.2 together show that adaptivity enables an exponential improvement in the distribution-free query complexity of testing juntas. This is in sharp contrast with uniform-distribution junta testing, where the adaptive and non-adaptive query complexities are polynomially related (with an exponent of only 3/2). To the best of our knowledge, this is the first example of a exponential separation between adaptive and nonadaptive distribution-free testers.

The algorithm. As a first step toward our $\tilde{O}(k^2)/\epsilon$-query algorithm, in Section 3, we first present a simple one-sided adaptive algorithm, which we call SimpleDJunta, that distribution-free tests $k$-juntas using $O({(k/ \epsilon)} + k \log n)$ queries. SimpleDJunta uses binary search and is an adaptation to the distribution-free setting of the $O({(k/ \epsilon)} + k \log n)$-query uniform-distribution algorithm, which is implicit in Blais (2009). The algorithm maintains a set $I$ of relevant variables: a string $x\in \lbrace 0,1\rbrace ^n$ has been found for each $i\in I$ such that $f(x)\ne f(x^{(i)})$ (we use $x^{(i)}$ to denote the string obtained by flipping the $i$th bit of $x$), and the algorithm rejects only when $|I|$ becomes larger than $k$. In each round, the algorithm samples a string $\mathbf {x}\leftarrow \mathcal {D}$ and a subset $\mathbf {R}$ of $\overline{I}:=[n]\setminus I$ uniformly at random. A simple lemma, Lemma 3.2, states that if $f$ is far from every $k$-junta with respect to $\mathcal {D}$, then $f(\mathbf {x})\ne f(\mathbf {x}^{(\mathbf {R})})$ with at least some moderately large probability as long as $|I|\le k$, where we use $\mathbf {x}^{(\mathbf {R})}$ to denote the string obtained from $\mathbf {x}$ by flipping every coordinate in $\mathbf {R}$. With such a pair $(\mathbf {x},\mathbf {x}^{(\mathbf {R})})$ in hand, it is straightforward to find a new relevant variable using binary search over coordinates in $\mathbf {R}$ (see Figure 1), with at most $\log n$ additional queries.

Fig. 1. Description of the standard binary search procedure.

To achieve a query complexity that is independent of $n$, clearly one must employ a more efficient approach than binary search over $\Omega (n)$ coordinates (since most likely the set $\mathbf {R}$ has size $\Omega (n)$ for the range of $k$ we are interested in). In the uniform-distribution setting this is accomplished in Blais (2009) by first randomly partitioning the variable space $[n]$ into $s=\mathrm{poly}(k/\epsilon)$ disjoint blocks $B_1,\ldots ,B_s$ of variables and carrying out binary search over blocks (see Figure 2) rather than over individual coordinates; this reduces the cost of each binary search to $\log (k/\epsilon)$ rather than $\log n$. The algorithm maintains a set of relevant blocks: two strings $x,y\in \lbrace 0,1\rbrace ^n$ have been found for each such block $B$ that satisfy $f(x)\ne f(y)$ and $y=x^{(S)}$ with $S\subseteq B$, and the algorithm rejects when more than $k$ relevant blocks have been found. In each round the algorithm samples two strings $\mathbf {x},\mathbf {y}$ uniformly at random conditioned on their agreeing with each other on the relevant blocks that have already been found in previous rounds; if $f(\mathbf {x})\ne f(\mathbf {y}),$ then the binary search over blocks is performed to find a new relevant block. To establish the correctness of this approach, Blais (2009) employs a detailed and technical analytic argument based on the influence of coordinates and the Efron-Stein orthogonal decomposition of functions over product spaces. This machinery is well suited for dealing with product distributions, and indeed the analysis of Blais (2009) goes through for any product distribution over $\lbrace 0,1\rbrace ^n$ (and even for more general finite domains and ranges). However, it is far from clear how to extend this machinery to work for the completely unstructured distributions $\mathcal {D}$ that must be handled in the distribution-free model.

Fig. 2. Description of the blockwise version of the binary search procedure.

Our main distribution-free junta testing algorithm, denoted MainDJunta, draws ideas from both SimpleDJunta (mainly Lemma 3.2) and the uniform distribution tester of (Blais 2009). To avoid the $\log n$ cost, the algorithm carries out binary search over blocks rather than over individual coordinates, and maintains a set of disjoint relevant blocks $B_1,\ldots ,B_\ell$, i.e., for each $B_j$ a pair of strings $x^j$ and $y^j$ have been found such that they agree with each other over $\overline{B_j}$ and satisfy $f(x^j)\ne f(y^j)$. Let $w^j$ be the projection of $x^j$ (and $y^j$) over $\overline{B_j}$ and let $g_j$ be the Boolean function over $\lbrace 0,1\rbrace ^{B_j}$ obtained from $f$ by setting variables in $\overline{B_j}$ to $w^j$. For clarity, we assume further that every function $g_j$ is very close to a literal (i.e., for some $\tau \in \lbrace x_{i_j},\overline{x_{i_j}}\rbrace$, we have $g_j(x)=\tau$ for all $x\in \lbrace 0,1\rbrace ^{B_j}$ for some $i_j\in B_j$) under the uniform distribution. (To justify this assumption, we note that if $g_j$ is far from every literal under the uniform distribution, then it is easy to split $B_j$ further into two relevant blocks using the uniform distribution algorithm of (Blais 2009).) Let $I=\lbrace i_j:j\in [\ell ]\rbrace$. Even though the algorithm does not know $I$, there is indeed a way to draw uniformly random subsets $\mathbf {R}$ of $\overline{I}$. First, we draw a partition of $B_j$ into $\mathbf {P}_j$ and $\mathbf {Q}_j$ uniformly at random, for each $j$. Since $g_j$ is close to a literal, it is not difficult to figure out whether $\mathbf {P}_j$ or $\mathbf {Q}_j$ contains the hidden $i_j$, say it is $\mathbf {P}_j$ for every $j$. Then the union of all $\mathbf {Q}_j$’s together with a uniformly random subset of $\overline{B_1\cup \cdots \cup B_\ell }$, denoted by $\mathbf {R}$, turns out to be a uniformly random subset of $\overline{I}$. With $\mathbf {R}$ in hand, Lemma 3.2 implies that $f(\mathbf {x})\ne f(\mathbf {x}^{(\mathbf {R})})$ with high probability when $\mathbf {x}\leftarrow \mathcal {D}$, and when this happens, one can carry out binary search over blocks to increase the number of relevant blocks by one. In Section 4.1, we explain the intuition behind the main algorithm in more detail.

The lower bound. As we explain in Section 2, a $q$-query non-adaptive distribution-free tester is a randomized algorithm $A$ that works as follows. When $A$ is run on an input pair $(\phi ,\mathcal {D})$ ¹ it is first given the result $(\mathbf {y}^1,\phi (\mathbf {y}^1)),\dots ,(\mathbf {y}^q,\phi (\mathbf {y}^q))$ of $q$ queries from the sampling oracle. Based on them, it queries the black-box oracle $q$ times on strings $\mathbf {z}^1,\dots ,\mathbf {z}^q.$ The $\mathbf {z}^j$’s may depend on the random pairs $(\mathbf {y}^i,\phi (\mathbf {y}^i))$ received from the sampling oracle, but the $j$th black-box query string $\mathbf {z}^j$ may not depend on the responses $\phi (\mathbf {z}^1),\dots ,\phi (\mathbf {z}^{j-1})$ to any of the $j-1$ earlier black-box queries.

As is standard in property testing lower bounds, our argument employs a distribution $ {\mathcal {YES}}$ over yes-instances and a distribution $ {\mathcal {NO}}$ over no-instances. Here, ${\mathcal {YES}}$ is a distribution over (function, distribution) pairs $(\mathbf {f},\boldsymbol {\mathcal {D}})$ in which $\mathbf {f}$ is guaranteed to be a $k$-junta; $ {\mathcal {NO}}$ is a distribution over pairs $(\mathbf {g},\boldsymbol {\mathcal {D}})$ such that with probability $1-o(1)$, $\mathbf {g}$ is $1/3$-far from every $k$-junta with respect to $\boldsymbol {\mathcal {D}}.$ To prove the desired lower bound against non-adaptive distribution-free testers, it suffices to show that for $q=2^{k/3}$, any deterministic non-adaptive algorithm $A$ as described above is roughly equally likely to accept whether it is run on an input drawn from ${\mathcal {YES}}$ or from $ {\mathcal {NO}}.$

Our construction of the ${\mathcal {YES}}$ and $ {\mathcal {NO}}$ distributions is essentially as follows. In making a draw either from ${\mathcal {YES}}$ or from $ {\mathcal {NO}}$, first $m=\Theta (2^k \log n)$ strings are selected uniformly at random from $\lbrace 0,1\rbrace ^n$ to form a set $\mathbf {S}$, and the distribution $\boldsymbol {\mathcal {D}}$ in both ${\mathcal {YES}}$ and $ {\mathcal {NO}}$ is set to be the uniform distribution over $\mathbf {S}$. Also, in both ${\mathcal {YES}}$ and $ {\mathcal {NO}}$, a “background” $k$-junta $\mathbf {h}$ is selected uniformly at random by first picking a set $\mathbf {J}$ of $k$ variables at random and then a random truth table for $\mathbf {h}$ over the variables in $\mathbf {J}$. We view the variables in $\mathbf {J}$ as partitioning $\lbrace 0,1\rbrace ^n$ into $2^k$ disjoint “sections” depending on how they are set.

In the case of a draw from ${\mathcal {YES}}$, the Boolean function $\mathbf {f}$ that goes with the above-described $\boldsymbol {\mathcal {D}}$ is simply the background junta $\mathbf {f}=\mathbf {h}$. In the case of a draw from $ {\mathcal {NO}}$, the function $\mathbf {g}$ that goes with $\boldsymbol {\mathcal {D}}$ is formed by modifying the background junta $\mathbf {h}$ in the following way (roughly speaking; see Section 5.1 for precise details): for each $z \in \mathbf {S}$, we toss a fair coin $\mathbf {b}(z)$ and set the value of all the strings in $z$’s section that lie within Hamming distance $0.4n$ from $z$ (including $z$ itself) to $\mathbf {b}(z)$ (see Figure 7). Note that the value of $\mathbf {g}$ at each string in $\mathbf {S}$ is a fair coin toss, which is completely independent of the background junta $\mathbf {h}.$ Using the choice of $m$ it can be argued (see Section 5.1) that with high probability $\mathbf {g}$ is $1/3$-far from every $k$-junta with respect to $\boldsymbol {\mathcal {D}}$ as $(\mathbf {g},\boldsymbol {\mathcal {D}})\leftarrow {\mathcal {NO}}$.

The rough idea of why a pair $(\mathbf {f},\boldsymbol {\mathcal {D}}) \leftarrow {\mathcal {YES}}$ is difficult for a ($q=2^{k/3}$)-query non-adaptive algorithm $A$ to distinguish from a pair $(\mathbf {g},\boldsymbol {\mathcal {D}}) \leftarrow {\mathcal {NO}}$ is as follows. Intuitively, in order for $A$ to distinguish the no-case from the yes-case, it must obtain two strings $x^1,x^2$ that belong to the same section but are labeled differently. Since there are $2^k$ sections but $q$ is only $2^{k/3}$, by the birthday paradox it is very unlikely that $A$ obtains two such strings among the $q$ samples $\mathbf {y}^1,\dots ,\mathbf {y}^q$ that it is given from the distribution $\boldsymbol {\mathcal {D}}$. In fact, in both the yes and no cases, writing $(\boldsymbol {\phi },\boldsymbol {\mathcal {D}})$ to denote the (function, distribution) pair, the distribution of the $q$ pairs $(\mathbf {y}^1,\boldsymbol {\phi }(\mathbf {y}^1)),\dots ,(\mathbf {y}^q,\boldsymbol {\phi }(\mathbf {y}^q))$ will be statistically very close to $(\mathbf {x}^1,\mathbf {b}_1),\dots ,(\mathbf {x}^q,\mathbf {b}_q)$, where each pair $(\mathbf {x}^j,\mathbf {b}_j)$ is independently drawn uniformly from $\lbrace 0,1\rbrace ^n \times \lbrace 0,1\rbrace$. Intuitively, this translates into the examples $(\mathbf {y}^i,\boldsymbol {\phi }(\mathbf {y}^i))$ from the sampling oracle “having no useful information” about the set $\mathbf {J}$ of variables that the background junta depends on.

What about the $q$ strings $\mathbf {z}^1,\dots ,\mathbf {z}^q$ that $A$ feeds to the black-box oracle? It is also unlikely that any two elements of $\mathbf {y}^1,\dots ,\mathbf {y}^q,\mathbf {z}^1,\dots ,\mathbf {z}^q$ belong to the same section but are labeled differently. Fix an $i \in [q]$, we give some intuition here as to why it is very unlikely that there is any $j$ such that $\mathbf {z}^i$ lies in the same section as $\mathbf {y}^j$ but has $f(\mathbf {z}^i) \ne f(\mathbf {y}^j)$ (via a union bound, the same intuition handles all $i \in [q]$). Intuitively, since the random examples from the sampling oracle provide no useful information about the set $\mathbf {J}$ defining the background junta, the only thing that $A$ can do in selecting $\mathbf {z}^i$ is to choose how far it lies, in terms of Hamming distance, from the points in $\mathbf {y}^1,\dots ,\mathbf {y}^q$ (which, recall, are uniform random). Fix $j \in [q]$, if $\mathbf {z}^i$ is within Hamming distance $0.4n$ from $\mathbf {y}^j$, then even if $\mathbf {z}^i$ lies in the same section as $\mathbf {y}^j$ it will be labeled the same way as $\mathbf {y}^j$, whether we are in the yes-case or the no-case. However, if $\mathbf {z}^i$ is farther than $0.4n$ in Hamming distance from $\mathbf {y}^j$, then it is overwhelmingly likely that $\mathbf {z}^i$ will lie in a different section from $\mathbf {y}^j$ (since it is very unlikely that all $0.4n$ of the flipped coordinates avoid the $k$-element set $\mathbf {J}$). We prove Theorem 1.2 in Section 5 via a formal argument that proceeds somewhat differently from but is informed by the above intuitions.

Organization. In Section 2, we define the distribution-free testing model and introduce some useful notation. In Section 3 we present SimpleDJunta and prove Lemma 3.2 in its analysis. In Section 4, we present our main algorithm MainDJunta and prove Theorem 1.1, and in Section 5, we prove Theorem 1.2.

Recall that the factor of $\log n$ in the query complexity of SimpleDJunta from the previous section is due to the use of the standard binary search procedure. To avoid it, one could choose to terminate each call to binary search early but this ends up giving us relevant blocks of variables instead of relevant variables. To highlight the challenge, imagine that the algorithm has found so far $\ell \le k$ many pairwise disjoint relevant blocks $B_j$, $j\in [\ell ]$; i.e., it has found a distinguishing pair for each block $B_j$. By definition, each $B_j$ must contain at least one relevant variable $i_j\in B_j$. However, we do not know exactly which variable in $B_j$ is $i_j$, and thus it is not clear how to draw a set $\mathbf {R}$ from $\overline{I}$ uniformly at random, where $I=\lbrace i_j:j\in [\ell ]\rbrace$, as on line 3 of SimpleDJunta, to apply Lemma 3.2 to discover a new relevant block. It seems that we are facing a dilemma when trying to improve SimpleDJunta to remove the $\log n$ factor: unless we pin down a set of relevant variables, it is not clear how to draw a random set from their complement, but pinning down a single relevant variable using the standard binary search procedure would already cost $\log n$ queries.

To explain the main idea behind our $ {\tilde{O}(k^2)/\epsilon }$-query algorithm, let us assume again that $\ell \le k$ many disjoint relevant blocks $B_j$ have been found so far, with a distinguishing pair $(x^{[j]},y^{[j]})$ for each $B_j$ (satisfying that $\mathsf {diff}(x^{[j]},y^{[j]})\subseteq B_j$ and $f(x^{[j]})\ne f(y^{[j]})$ by definition). Let

To make progress, we draw a random two-way partition of each $B_j$ into $\mathbf {P}_j$ and $\mathbf {Q}_j$, i.e., each $i\in B_j$ is added to $\mathbf {P}_j$ or $\mathbf {Q}_j$ with probability $1/2$ (so they are disjoint and $B_j=\mathbf {P}_j\cup \mathbf {Q}_j$). We make three simple but crucial observations to increase the number of disjoint relevant blocks by one.

1. Since $g_j$ is assumed to be a literal on the $i_j$th variable (and by the definition of $g_j$ we have query access to $g_j$), it is easy to tell whether $i_j\in \mathbf {P}_j$ or $i_j\in \mathbf {Q}_j$, simply by picking an arbitrary string $x \in \lbrace 0,1\rbrace ^{B_j}$ and comparing $g_j(x)$ with $g_j(x^{(\mathbf {P}_j)})$. Below, we assume that the algorithm correctly determines whether $i_j$ is in $\mathbf {P}_j$ or $\mathbf {Q}_j$ for all $j \in [\ell ]$. We let $\mathbf {S}_j$ denote the element of $\lbrace \mathbf {P}_j,\mathbf {Q}_j\rbrace$ that contains $i_j$ and let $\mathbf {T}_j$ denote the other one. We also assume below that the algorithm has obtained a distinguishing pair of $g_j$ for each block $\mathbf {S}_j$.
   
2. Next, we draw a subset $\mathbf {T}$ of $\overline{B_1\cup \cdots \cup B_\ell }$ uniformly at random. Crucially, the way that $\mathbf {P}_j$ and $\mathbf {Q}_j$ were drawn, and the above assumption that $\mathbf {S}_j$ contains $i_j$, implies that
   \[ \mathbf {R}:=\mathbf {T}\cup \mathbf {T}_1\cup \cdots \cup \mathbf {T}_\ell \]
   is indeed a subset of $\overline{I}$ drawn uniformly at random (recall that $I=\lbrace i_j:j\in [\ell ]\rbrace$), since other than those in $I$, each variable is included in $\mathbf {R}$ independently with probability $1/2$. If we draw a random string $\mathbf {x}\leftarrow \mathcal {D}$, then Lemma 3.2 implies that $f(\mathbf {x})\ne f(\mathbf {y})$, where $\mathbf {y}=\mathbf {x}^{(\mathbf {R})}$, with probability at least $\epsilon /2$.
   
3. Finally, assuming that $f(\mathbf {x})\ne f(\mathbf {y})$ (with $\mathsf {diff}(\mathbf {x},\mathbf {y})=\mathbf {R}$), running the blockwise binary search on $\mathbf {x},\mathbf {y}$ and blocks $\mathbf {T},\mathbf {T}_1,\ldots ,\mathbf {T}_\ell$ will lead to a distinguishing pair for one of these blocks and will only require $O(\log \ell) \le O(\log k)$ queries. If it is a distinguishing pair for $\mathbf {T}$, then we can add $\mathbf {T}$ to the list of relevant blocks $B_1,\ldots ,B_\ell$ and they remain pairwise disjoint. If it is $\mathbf {T}_j$ for some $j\in [\ell ]$, then we can replace $B_j$ in the list by $\mathbf {S}_j$ and $\mathbf {T}_j$, for each of which we have found a distinguishing pair (recall that a distinguishing pair has already been found for each $\mathbf {S}_j$ in the first step). In either case, we have that the number of pairwise disjoint relevant blocks grows by one.
   

Coming back to the assumption we made earlier, although $g_j$ is very unlikely to be a literal, it must fall into one of the following three cases: (1) close to a literal; (2) close to a (all-0 or all-1) constant function; or (3) far from 1-juntas. Here in all cases “close” and “far” means with respect to the uniform distribution over $\lbrace 0,1\rbrace ^{B_j}$. As we discuss in more detail in the rest of the section, with some more careful probability analysis the above arguments generalize to the case in which every $g_j$ is only close to (rather than exactly) a literal. However, if one of the blocks $B_j$ is in case (2) or (3), then (using the fact that we have a distinguishing pair for $B_j$) it is easy to split $B_j$ into two blocks and find a distinguishing pair for each of them. (For example, for case (3) this can be done by running Blais's uniform distribution junta testing algorithm.) As a result, we can always make progress by increasing the number of pairwise disjoint relevant blocks by one. Our algorithm basically keep repeating these steps until the number of such blocks reaches $k+1$.

Our algorithm MainDJunta $(f,\mathcal {D},k,\epsilon)$ is described in Figure 4. It maintains two collections of blocks $V=\lbrace B_1,\ldots ,B_v\rbrace$ ($V$ for “verified”) and $U=\lbrace C_1,\ldots ,C_u\rbrace$ ($U$ for “unverified”) for some nonnegative integers $v$ and $u$. They are set to be $\emptyset$ at initialization and always satisfy the following properties:

Fig. 4. Description of the distribution-free testing algorithm MainDJunta for $k$-juntas.

• $B_1,\ldots ,B_v,C_1,\ldots ,C_u\subseteq [n]$ are pairwise disjoint (nonempty) blocks of variables;
  
• A distinguishing pair has been found for each of these blocks. For notational convenience, we use $(x^{[j]},y^{[j]})$ to denote the distinguishing pair for each $B_j$ and $(x^{[C]},y^{[C]})$ to denote the distinguishing pair for each block $C\in U$. We also use the notation
  \[ w^{[j]}:=\big(x^{[j]}\big)_{\overline{B_j}}=\big(y^{[j]}\big)_{\overline{B_j}}\in \lbrace 0,1\rbrace ^{\overline{B_j}}\quad {\rm and}\quad w^{[C]}:=\big(x^{[C]}\big)_{\overline{C}}=\big(y^{[C]}\big)_{\overline{C}}\in \lbrace 0,1\rbrace ^{\overline{C}}, \]
  and we let and , Boolean functions over $\lbrace 0,1\rbrace ^{B_j}$ and $\lbrace 0,1\rbrace ^C$, respectively.
  

The algorithm rejects only when the total number of blocks $v+u\ge k+1$ so it is one-sided.

Throughout the algorithm and its analysis, we set a key parameter $ \gamma := 1/(8k).$ Blocks in $V$ are intended to be those that have been “verified” to satisfy the condition that $g_j$ is $\gamma$-close to a literal (for some unknown variable $i_j\in B_j$) under the uniform distribution, while blocks in $U$ have not been verified yet so they may or may not satisfy the condition. More formally, at any point in the execution of the algorithm we say that the algorithm is in good condition if its current collections $V$ and $U$ satisfy conditions (A), (B), and

1. Every $g_j$, $j\in [v]$, is $\gamma$-close to a literal under the uniform distribution over $\lbrace 0,1\rbrace ^{B_j}$.
   

The algorithm MainDJunta $(f,k,\epsilon)$ starts with $V=U=\emptyset$ and proceeds round by round. For each round, we consider two different types that the round may have: type 1 is that $u=0$, and type 2 is that $u\gt 0$. In a type-1 round (with $u=0$), we follow the idea sketched in Section 4.1 to increase the total number of disjoint relevant blocks by one. We prove the following lemma for this case in Section 4.3.

In a type-2 round (with $u\ge 1$), we pick an arbitrary block $C$ from $U$ and check whether $g_C$ is close to a literal under the uniform distribution. The following lemma, which we prove in Section 4.4, shows that with high probability, either $C$ is moved to collection $V$ and the algorithm remains in good condition, or the algorithm finds two disjoint subsets of $C$ and a distinguishing pair for each of them so that $V$ stays the same but $|U|$ goes up by one (we add these two blocks to $U$, since they have not yet been verified).

Assuming Lemmas 4.1 and 4.2, we are ready to prove the correctness of MainDJunta.

Proof of Theorem 4.3 Assuming Lemmas 4.1 and 4.2. MainDJunta is one-sided, since it rejects $f$ only when it has found $k+1$ pairwise disjoint relevant blocks of $f$. Its query complexity is

\begin{align*} &\mbox{(# type-1 rounds)$\cdot $(# queries per type-1 round) $ + $ (# type-2 rounds)$\cdot $(# queries per type-2 round)}\\ &= O(k/\epsilon)\cdot (O(k)+O(\log k))+ O(k)\cdot O(\log k)\cdot O(k) =O(k^2/\epsilon)+O(k^2\log k)=O(k^2\log k)/\epsilon . \end{align*}

In the rest of the proof we show that it rejects $f$ with probability at least $2/3$ when $f$ is $\epsilon$-far from every $k$-junta with respect to $\mathcal {D}$.

For this purpose, we introduce a simple potential function $F$ to measure the progress:

\[ F(V,U):={3|V|+2|U|}. \]

Each round of the algorithm is either of type-1 (when $|U|=0$) or of type-2 (when $|U|\gt 0$). By Lemma 4.1, if the algorithm is in good condition at the beginning of a type-1 round, then the algorithm ends the round in good condition and the potential function $F$ goes up by at least one with probability at least $\epsilon /4$ (in which case, we say that the algorithm succeeds in this type-1 round). By Lemma 4.2, if the algorithm is in good condition at the beginning of a type-2 round, then the algorithm ends the round in good condition and $F$ goes up by at least one with probability at least $1-1/(32k)$ (in which case, we say it succeeds in this type-2 round).

Note that $F$ is 0 at the beginning ($V=U=\emptyset$) and that we must have $|U|+|V|\ge k+1$ (and thus, the algorithm rejects) when the potential function $F$ reaches $ {3(k+1)}$ or above. As a result, a necessary condition for the algorithm to accept is that one of the following two events occurs:

1. $E_1$: At least one of the (no more than ${3(k+1)}$ many) type-2 rounds fails.
   
2. $E_2$: $E_1$ does not occur (so the algorithm ends every round in good condition, and the reason that the algorithm accepts cannot be that it uses up all the $3(k+1)$ many type-2 rounds), and the algorithm uses up all the ${64}k/\epsilon$ many type-1 rounds but at most $3k+2$ of them succeed.
   

By a union bound, the probability of $E_1$ is at most

\[ {3(k+1)\cdot 1/(64k)\le 6k\cdot 1/(64k)\lt 1/8.} \]

As the algorithm ends every round in good condition, it follows from Lemma 4.1 from a coupling argument that the probability of $E_2$ is at most the probability that

\[ \sum _{i=1}^{{64k/\epsilon }} \mathbf {Z}_i\le {3k+2}, \]

where $\mathbf {Z}_i$’s are i.i.d. $\lbrace 0,1\rbrace$-valued random variables that take 1 with probability $\epsilon /4$. It follows from the Chernoff bound the probability is at most (using $3k+2\le 5k$)

\[ {\exp \left(-\left(\frac{11}{16}\right)^2\cdot \frac{16k}{2}\right)=\exp \left(-\frac{121k}{32}\right) \lt \exp (-3)\lt 1/8.} \]

Finally, it follows from a union bound that the algorithm rejects with probability at least $3/4$.

We start with a lemma for the subroutine WhereIsTheLiteral, which is described in Figure 5.

Fig. 5. Description of the subroutine WhereIsTheLiteral.

Proof. Let $K$ be the set of strings $x\in \lbrace 0,1\rbrace ^B$ such that $g(x)$ disagrees with the literal to which it is $\gamma$-close (so $|K|\le \gamma \cdot 2^{|B|}$). We work on the case when $i\in Q$; the case when $i\in P$ is similar.

By the description of WhereIsTheLiteral, it returns a distinguishing pair for $Q$ if

\[ g(\mathbf {w}\circ \mathbf {z})=g(\mathbf {w}\circ \mathbf {z}^{(P)})\quad {\rm and}\quad g(\mathbf {w}^{\prime }\circ \mathbf {z}^{\prime })\ne g(\mathbf {w}^{\prime }\circ \mathbf {z}^{\prime (Q)}). \]

Note that this holds if all four strings fall outside of $K$ and thus, the probability that it does not hold is at most the probability that at least one of these four strings falls inside $K$. The latter by a union bound is at most $4\gamma$, since each of these four strings is drawn uniformly at random from $\lbrace 0,1\rbrace ^B$ by itself. This finishes the proof of the lemma.

We are now ready to prove Lemma 4.1.

Proof of Lemma 4.1. First, it is easy to verify that if the algorithm starts a round in good condition, then it ends it in good condition. This is because whenever a block is added to $U$, it is disjoint from other blocks, and we have found a distinguishing pair for it.

Next it follows directly from Lemma 4.4 and a union bound that, for any sequence of partitions $P_j$ and $Q_j$ of $B_j$ picked on line 6, the probability that the for-loop correctly sets $\mathbf {S}_j$ to be the one that contains the special variable $i_j$ for all $j\in [v]$ is at least (recalling that $\gamma =1/(8k)$)

\[ 1-4\gamma \cdot v \ge 1-4\gamma \cdot k= 1/2. \]

Now, we can view the process equivalently as follows. First, we draw $\mathbf {x}\leftarrow \mathcal {D}$, $\mathbf {T}\leftarrow \overline{B_1\cup \cdots \cup B_v}$, and random partitions $\mathbf {P}_j,\mathbf {Q}_j$ of each $B_j$. If we let $\mathbf {T}^*_j$ be the set in $\mathbf {P}_j,\mathbf {Q}_j$ that does not contain the special variable, then $\mathbf {R}^*=\mathbf {T}\cup \mathbf {T}^*_1\cup \cdots \cup \mathbf {T}^*_v$ is a set drawn uniformly at random from $\overline{I}$, where $I=\lbrace i_j:j\in [v]\rbrace$ consists of the special variables. Therefore, it follows from Lemma 3.2 that $f(\mathbf {x})\ne f(\mathbf {x}^{(\mathbf {R}^*)})$ with probability at least $\epsilon /2$. Since with probability at least $1/2$, the set $\mathbf {R}$ on line 11 agrees with $\mathbf {R}^*$, we have that the algorithm reaches line 12 with $f(\mathbf {x})\ne f(\mathbf {y})$ with probability at least $\epsilon /4$. Given this, the lemma is immediate by inspection of lines 12-17 of the algorithm.

First it follows from the description of the subroutine Literal $(g)$ in Figure 6 that it either returns “true” or a pair of nonempty disjoint subsets $C^{\prime },C^*$ of $C$ and a distinguishing pair of $g$ for each of them (see Theorem 2.3). Next, let $C \in V$ be the block picked in line 20. If $g$ is $\gamma$-close to a literal, then it is easy to verify that one of the two events described in Lemma 4.2 must hold (using the property of Literal $(g)$ above). So, we focus on the other two cases in the rest of the proof: $g$ is $\gamma$-far from 1-juntas or $g$ is $\gamma$-close to a (all-1 or all-0) constant function. In both cases, we show below that the second event happens with high probability.

Fig. 6. Description of the subroutine Literal.

When $g$ is $\gamma$-far from 1-juntas under the uniform distribution, we have that one of the $ {\log k+6}$ calls to UniformJunta in Literal rejects with probability at least

When $g$ is $\gamma$-close to a constant function (say the all-1 function), we have that either string $x$ or $y$ in the distinguishing pair for $C$ disagrees with the function (say $g(x)=0$, since $g(x)\ne g(y)$). Let $K$ be the set of strings in $\lbrace 0,1\rbrace ^C$ that disagree with the all-1 function. Then line 7 of Literal $(g)$ does not hold only when one of $x^{(\mathbf {C}^{\prime })}$ or $x^{(\mathbf {C}^*)}$ lies in $K$. As both strings are distributed uniformly over $\lbrace 0,1\rbrace ^C$ by themselves, this happens with probability at most $2\gamma$ by a union bound. Therefore, the probability that line 7 holds at least once is at least

This finishes the proof of Lemma 4.2.

Given $J\subseteq [n]$, we partition $\lbrace 0,1\rbrace ^n$ into sections (with respect to $J$) where the $z$-section, $z\in \lbrace 0,1\rbrace ^J$, consists of those $x\in \lbrace 0,1\rbrace ^n$ that have $x_J=z$. We write $\mathcal {JUNTA}_J$ to denote the uniform distribution over all juntas over $J$. More precisely, a Boolean function $\mathbf {h}:\lbrace 0,1\rbrace ^n\rightarrow \lbrace 0,1\rbrace$ drawn from $\mathcal {JUNTA}_J$ is generated as follows: For each $z\in \lbrace 0,1\rbrace ^J$, a bit $\mathbf {b}(z)$ is chosen independently and uniformly at random, and for each $x \in \lbrace 0,1\rbrace ^n$ the value of $\mathbf {h}(x)$ is set to $\mathbf {b}(x_J)$. Let

We start with ${\mathcal{YES}}$. A pair $(\mathbf {f},\boldsymbol {\mathcal {D}})$ drawn from ${\mathcal{YES}}$ is generated as follows:

1. First, we draw independently a subset $\mathbf {J}$ of $[n]$ of size $k$ uniformly at random and a subset $\mathbf {S}$ of $\lbrace 0,1\rbrace ^n$ of size $m$ uniformly at random.
   
2. Next, we draw $\mathbf {f}\leftarrow \mathcal {JUNTA}_\mathbf {J}$ and set $\boldsymbol {\mathcal {D}}$ to be the uniform distribution over $\mathbf {S}$.
   

For technical reasons that will become clear in Section 5.2 we use ${\mathcal{YES}}^*$ to denote the probability distribution supported over triples $(f,\mathcal {D},J)$, with $(\mathbf {f},\boldsymbol {\mathcal {D}},\mathbf {J})\leftarrow {\mathcal{YES}}^*$ being generated by the same two steps above (so, the only difference is that we include $\mathbf {J}$ in elements of ${\mathcal{YES}}^*$).

The following observation is straightforward from the definition of ${\mathcal{YES}}$.

We now describe $\mathcal {NO}.$ A pair $(\mathbf {g},\boldsymbol {\mathcal {D}})$ drawn from $\mathcal {NO}$ is generated as follows:

1. We draw $\mathbf {J}$ and $\mathbf {S}$ in the same way as the first step of ${\mathcal{YES}}$.
   
2. Next, we draw $\mathbf {h}\leftarrow \mathcal {JUNTA}_\mathbf {J}$ and a map $\boldsymbol {\gamma }:\mathbf {S}\rightarrow \lbrace 0,1\rbrace$ uniformly at random by choosing a bit independently and uniformly at random for each string in $\mathbf {S}$. We usually refer to $\mathbf {h}$ as the “background junta.”
   
3. The distribution $\boldsymbol {\mathcal {D}}$ is set to be the uniform distribution over $\mathbf {S}$, which is the same as ${\mathcal{YES}}$. The function $\mathbf {g}: \lbrace 0,1\rbrace ^n \rightarrow \lbrace 0,1\rbrace$ is defined using $\mathbf {h},\mathbf {S}$ and $\boldsymbol {\gamma }$ as follows:
   
   1. For each string $y \in \mathbf {S}$, set $\mathbf {g}(y)=\boldsymbol {\gamma }(y)$;
      
   2. For each string $x\notin \mathbf {S}$, if there exists no $y\in \mathbf {S}$ with ${y_\mathbf {J}=x_\mathbf {J}}$ and $d(x,y)\le 0.4n$, set $\mathbf {g}(x)=\mathbf {h}(x)$; otherwise, we set $\mathbf {g}(x)=1$ if there exists such a $y\in \mathbf {S}$ with $\boldsymbol {\gamma }(y)=1$, and set $\mathbf {g}(x)=0$ if every such $y\in \mathbf {S}$ has $\boldsymbol {\gamma }(y)=0$. (The choice of the tie-breaking rule here is not important; we just pick one to make sure that $\mathbf {g}$ is well defined in all cases.)
      

Similarly, we let $\mathcal {NO}^*$ denote the distribution supported on triples $(g,\mathcal {D},J)$ as generated above.

See Figure 7 for an illustration of a function drawn from $\mathcal {NO}$. To gain some intuition, we first note that about half of the strings $z\in S$ have $g(z)$ disagree with the value of the background junta on the section it lies in. With such a string $z$ in hand (from one of the samples received in the first phase), an algorithm may attempt to find a string $w$ that lies in the same section as $z$ but satisfies $g(z)\ne g(w)$. If such a string is found, then the algorithm knows for sure that $(g,\mathcal {D})$ is from the $\mathcal {NO}$ distribution. However, finding such a $w$ is not easy, because one must flip more than $0.4n$ bits of $z$, but without knowing the variables in $J$ it is hard to keep $w$ in the same section as $z$ after flipping this many bits.

Fig. 7. A schematic depiction of how $\lbrace 0,1\rbrace ^n$ is labeled by a function $g$ from $\mathcal {NO}$. The domain $\lbrace 0,1\rbrace ^n$ is partitioned into $2^k$ sections corresponding to different settings of the variables in $J$; each section is a vertical strip in the figure. Shaded regions correspond to strings where $g$ evaluates to 1 and unshaded regions to strings where $g$ evaluates to 0. Each string in $S$ is a black dot and the value of $g$ on each such string is chosen uniformly at random. Since in this figure the truncated circles are disjoint, the tie-breaking rule does not come into effect, and for each $z \in S$, all strings in its section within distance at most $0.4n$ (the points in the truncated circle around $z$) have the same value as $z$. The value of $g$ on other points is determined by the background junta $h$, which assigns a uniform random bit to each section.

Next, we prove that with high probability, $(\mathbf {g},\boldsymbol {\mathcal {D}})\leftarrow \mathcal {NO}$ satisfies that $\mathbf {g}$ is $1/3$-far from every $k$-junta with respect to $\boldsymbol {\mathcal {D}}$:

Proof. Fix a $k$-junta $h$, i.e., any set $I \subset [n]$ with $|I|=k$ and any $2^k$-bit truth table over variables in $I$. We have that $\mathsf {dist}_{\boldsymbol {\mathcal {D}}}(\mathbf {g},h)$ is precisely the fraction of strings $z \in \mathbf {S}$ such that $\boldsymbol {\gamma }(z) \ne h(z).$ Since each bit $\boldsymbol {\gamma }(z)$ is drawn independently and uniformly at random, we have that

\[ \Pr _{(\mathbf {g},\boldsymbol {\mathcal {D}}) \leftarrow \mathcal {NO}}\ [\hspace{1.70709pt}\mathsf {dist}_{\boldsymbol {\mathcal {D}}}(\mathbf {g},h) \le 1/3 \hspace{1.70709pt} ] = \Pr _{\mathbf {j}\leftarrow \mathrm{Bin}(m,1/2)} [\hspace{1.70709pt}\mathbf {j}\le m/3 \hspace{1.70709pt} ], \]

which, recalling that $m=36 \cdot 2^k \ln n$, by a standard Chernoff bound is at most $e^{-m/36} = n^{-2^k}.$ The result follows by a union bound over all (at most)

\[ \binom{n}{k}\cdot 2^{2^k} \le n^k\cdot 2^{2^k}=o_k\big(n^{2^k}\big) \]

possible $k$-juntas $h$ over $n$ variables. This finishes the proof of the lemma.

Given Lemmas 5.2 and 5.3, to prove Theorem 1.2 it remains only to prove Lemma 5.1.

The following definitions will be useful. Let $Y=(y^i:i\in [q])$ be a sequence of $q$ strings in $\lbrace 0,1\rbrace ^n$, $\alpha$ be a $q$-bit string, and $J\subset [n]$ be a set of variables of size $k$. We say that $(Y,\alpha ,J)$ is consistent if

To prove Lemma 5.1, we first derive from $A$ a new randomized algorithm $A^{\prime }$ that works on triples $(\phi ,\mathcal {D},J)$ from the support of either ${\mathcal{YES}}^*$ or $\mathcal {NO}^*$. Again for clarity we use $\phi$ to denote a function from the support of ${\mathcal{YES}}$/${\mathcal{YES}}^*$ or $\mathcal {NO}$/$\mathcal {NO}^*$, $f$ to denote a function from ${\mathcal{YES}}$/${\mathcal{YES}}^*$ and $g$ to denote a function from $\mathcal {NO}$/$\mathcal {NO}^*$.

In addition to being randomized, $A^{\prime }$ differs from $A$ in two important ways:

1. Like $A$, $A^{\prime }$ receives samples $\mathbf {Y}\leftarrow \mathcal {D}^q$ and $\phi (\mathbf {Y})$, but unlike $A$, $A^{\prime }$ also receives $J$ for free.
   
2. Unlike $A$, $A^{\prime }$ does not make any black-box queries but simply runs on the triple $(\mathbf {Y},\phi (\mathbf {Y}),J)$ it receives at the beginning. So formally $A^{\prime }$ is a randomized algorithm that runs on triples $(Y,\alpha ,J)$, where $Y=(y^i:i\in [q])$ is a sequence of $q$ strings, $\alpha$ is a $q$-bit string, and $J\subset [n]$ is a set of variables of size $k$, and outputs “accept” or “reject.”
   

A detailed description of the randomized algorithm $A^{\prime }$ running on $(Y,\alpha ,J)$ is as follows:

1. First, if $(Y,\alpha ,J)$ is not consistent, then $A^{\prime }$ immediately halts and rejects (simply because this can never occur if $(Y,\alpha ,J)$ is obtained from a triple $(f,\mathcal {D},J)$ in the support of ${\mathcal{YES}}^*$). Otherwise, $A^{\prime }$ applies $A_1$ on $(Y,\alpha)$ to obtain a sequence $Z=(Z^i:i\in [q])$ of $q$ strings.
   
2. Next, $A^{\prime }$ draws $\mathbf {h}^{\prime } \leftarrow \mathcal {JUNTA}_{Y,\alpha ,J}$. (This is the only part of $A^{\prime }$ that is randomized.)
   
3. Finally, $A^{\prime }$ runs $A_2(Y,\alpha ,\mathbf {h}^{\prime }(Z))$ and outputs the same result (accept or reject).
   

From the description of $A^{\prime }$ above, whether it accepts a triple $(\phi ,\mathcal {D},J)$ or not depends on both the randomness of $\mathbf {Y}$ and $\mathbf {h}^{\prime }$. Formally, we have

Lemma 5.1 follows immediately from the following three lemmas (note that the marginal distribution of $(\mathbf {f},\boldsymbol {\mathcal {D}})$ in ${\mathcal{YES}}^*$ (or $(\mathbf {g},\boldsymbol {\mathcal {D}})$ in $\mathcal {NO}^*$) is the same as ${\mathcal{YES}}$ (or $\mathcal {NO}$)). In all three lemmas, we assume that $A$ is a $q$-query non-adaptive deterministic algorithm while $A^{\prime }$ is the randomized algorithm derived from $A$ as described above.

We start with the proof of Lemma 5.4, which says that a limited algorithm such as $A^{\prime }$ cannot effectively distinguish between a draw from ${\mathcal{YES}}^*$ versus $\mathcal {NO}^*$:

Fix any $(Y,J)$ in the support of $(\mathbf {Y},\mathbf {J})$ such that $Y$ is scattered by $J$. We claim that the distributions of $\boldsymbol {\alpha }$ conditioning on $(\mathbf {Y},\mathbf {J})=(Y,J)$ in the ${\mathcal{YES}}^*$ case and the $\mathcal {NO}^*$ case are identical, from which it follows that the total variation distance between the distributions of $(\mathbf {Y},\boldsymbol {\alpha },\mathbf {J})$ in the two cases is at most $O(2^{- k/3})\le 1/8$ when $k$ is sufficiently large. Indeed, $\boldsymbol {\alpha }$ is uniform over strings of length $q$ in both cases. This is trivial for $\mathcal {NO}^*$. For ${\mathcal{YES}}^*$ note that $\boldsymbol {\alpha }$ is determined by the random $k$-junta $\mathbf {f}\leftarrow \mathcal {JUNTA}_J$; the claim follows from the assumption that $Y$ is scattered by $J$.

Proof of Claim 5.7. We fix $J$ and show that $\mathbf {Y}$ is scattered by $J$ with high probability. As strings of $\mathbf {Y}$ are drawn one by one, the probability of $\mathbf {y}^i$ colliding with one of the previous samples is at most $(i-1)/m\le q/m$. By a union bound, all strings in $\mathbf {Y}$ are distinct with probability at least

\[ 1-q\cdot (q/m)=1-q^2/m=1-O\big(2^{-k/3}\big). \]

Conditioning on this event, $\mathbf {Y}=(\mathbf {y}^i)$ is distributed precisely as a uniform random sequence from $\lbrace 0,1\rbrace ^n$ with no repetition and thus each pair $(\mathbf {y}^i,\mathbf {y}^j)$ is distributed uniformly over pairs of distinct strings in $\lbrace 0,1\rbrace ^n$. As a result, we have

\[ \Pr \big[\hspace{0.85355pt}\mathbf {y}^{i}_J=\mathbf {y}^{j}_J\hspace{1.42271pt}\big] =\frac{2^{n-k}-1}{2^n-1}\le \frac{1}{2^k}. \]

By a union bound over $({{q}\atop{2}})$ pairs, we have that the probability of $\mathbf {Y}$ being scattered by $J$ is at least

\[ (1-O(2^{-k/3}))\cdot \left(1-\binom{q}{2}\cdot 2^{-k}\right)\ge 1-O(2^{-k/3}). \]

This finishes the proof of the claim.

Next, we prove Lemma 5.5.

Finally, we prove Lemma 5.6, the most difficult among the three lemmas:

We delay the proof of the following claim to the end.

Fix any good $(Y,\alpha ,J,\mathcal {D})$ in the support and let $Z=A_1(Y,\alpha)$. We finish the proof by showing that the distribution of $\mathbf {g}(Z)$, a binary string of length $q$, conditioning on $(\mathbf {Y},\boldsymbol {\alpha },\mathbf {J},\boldsymbol {\mathcal {D}})=(Y,\alpha ,J,\mathcal {D})$ is the same as that of $\mathbf {h}^{\prime }(Z)$ with $\mathbf {h}^{\prime }\leftarrow \mathcal {JUNTA}_{Y,\alpha ,J}$. This combined with Claim 5.8 implies that the difference of the two probabilities has absolute value at most $1/8$.

To see this is the case, we partition strings of $Z$ into $Z_w$, where each $Z_w$ is a nonempty set that contains all $z$ in $Z$ with $z_J=w\in \lbrace 0,1\rbrace ^J$. For each $Z_w$, we consider the following two cases:

1. If there exists no string $y$ in $Y$ with $y_J=w$, then by $E_1$ strings in $Z_w$ are all far from strings of $S$ (i.e., the support of $\mathcal {D}$) in this section and thus, $\mathbf {g}(z)=\mathbf {b}(w)$ for some independent and uniform bit $\mathbf {b}(w)$, for all strings $z\in Z_w$.
   
2. If there exists a $y$ in $Y$ with $y_J=w$ (which must be unique by $E_0$), say $y^i$, then by $E_1$ and $E_2$ strings in $Z_w$ are all close to $y$ and far from other strings of $S$ in this section. As a result, we have $\mathbf {g}(z)=\alpha _i$ for all strings $z\in Z_w$.
   

So the conditional distribution of $\mathbf {g}(Z)$ is identical to that of $\mathbf {h}^{\prime }(Z)$ with $\mathbf {h}^{\prime }\hspace{-1.42271pt}\leftarrow \hspace{-1.42271pt}\mathcal {JUNTA}_{Y,\alpha ,J}$. This finishes the proof of the lemma.