In Chapter 1.6 we described the BLR property testing algorithm: given query access to an unknown function $f : \{0,1\}^n \to \{0,1\}$, this algorithm queries $f$ on a few random inputs and approximately determines whether $f$ has the property of being linear over ${\mathbb F}_2$. The field of *property testing* for boolean functions is concerned with coming up with similar algorithms for other properties.

In general, a “property” can be any collection $\mathcal{C}$ of $n$-bit boolean functions; it’s the same as the notion of “concept class” from learning theory. Indeed, before running an algorithm to try to learn an unknown $f \in \mathcal{C}$, one might first run a property testing algorithm to try to verify that indeed $f \in \mathcal{C}$.

Let’s encapsulate the key aspects of the BLR linearity test with some definitions:

Definition 1An$r$-query function testing algorithmfor boolean functions $f : \{0,1\}^n \to \{0,1\}$ is a randomized algorithm which:

- chooses $r$ (or fewer) strings ${\boldsymbol{x}}^{(1)}, \dots, {\boldsymbol{x}}^{(r)} \in \{0,1\}^n$ according to some probability distribution;
- queries $f({\boldsymbol{x}}^{(1)}), \dots, f({\boldsymbol{x}}^{(r)})$;
- based on the outcomes, decides (deterministically) whether to “accept” $f$.

Definition 2Let $\mathcal{C}$ be a “property” of $n$-bit boolean functions; i.e., a collection of functions $\{0,1\}^n \to \{0,1\}$. We say a function testing algorithm is alocal tester for $\mathcal{C}$(withrejection rate$\lambda > 0$) if it satisfies the following:

- If $f \in \mathcal{C}$ then the tester accepts with probability $1$.
- For all $0 \leq \epsilon \leq 1$, if $\mathrm{dist}(f,\mathcal{C}) > \epsilon$ (in the sense of Definition 1.30) then the tester rejects $f$ with probability greater than $\lambda \cdot \epsilon$. Equivalently, if the tester accepts $f$ with probability at least $1 – \lambda \cdot \epsilon$ then $f$ is $\epsilon$-close to $\mathcal{C}$; i.e., $\exists g \in \mathcal{C}$ such that $\mathrm{dist}(f,g) \leq \epsilon$.

By taking $\epsilon = 0$ in the above definition you see that any local tester gives a characterization of $\mathcal{C}$: a function is in $\mathcal{C}$ if and only if it is accepted by the tester with probability $1$. But a local tester furthermore gives a “robust” characterization: any function accepted with probability *close* to $1$ must be *close* to satisfying $\mathcal{C}$.

Example 3By Theorem 1.31, the BLR Test is a $3$-query local tester for the property $\mathcal{C} = \{f : {\mathbb F}_2^n \to {\mathbb F}_2 \mid f \text{ is linear}\}$ (with rejection rate $1$).

Remark 4To be pedantic, the BLR linearity test is actually a family of local testers, one for each value of $n$. This is a common scenario: we will usually be interested in testing naturalfamiliesof properties $(\mathcal{C}_n)_{n \in {\mathbb N}^+}$, where $\mathcal{C}_n$ contains functions $\{0,1\}^n \to \{0,1\}$. In this case we need to describe a family of testers, one for each $n$. Generally, these testers will “act the same” for all values of $n$ and will have the property that the rejection rate $\lambda > 0$ is a universal constant independent of $n$.

There are a number of standard variations of Definition 2 that one could consider. One variation is to allow for an *adaptive* testing algorithm, meaning that the algorithm can decide how to generate ${\boldsymbol{x}}^{(t)}$ based on the query outcomes $f({\boldsymbol{x}}^{(1)}), \dots, f({\boldsymbol{x}}^{(t-1)})$. However in this book we will only consider non-adaptive testing. Another variation is to relax the requirement that $\epsilon$-far functions be rejected with probability $\Omega(\epsilon)$; one could allow for smaller rates such as $\Omega(\epsilon^2)$, or $\Omega(\epsilon/\log n)$. For simplicity, we will stick with the strict demand that the rejection probability be linear in $\epsilon$. Finally, the most common definition of property testing allows the number of queries to be a function $r(\epsilon)$ of $\epsilon$ but requires that any function $\epsilon$-far from $\mathcal{C}$ be rejected with probability at least $1/2$. This is easier to achieve than satisfying Definition 2; see the exercises. So far we have seen that the property of being linear over ${\mathbb F}_2$ is locally testable. We’ll now spend some time discussing local testability of an even simpler property, the property of being a *dictator*. In other words, we’ll consider the property\[ {\mathcal D} = \{f : \{0,1\}^n \to \{0,1\} \mid f(x) = x_i \text{ for some $i \in [n]$}\}. \] As we will see, dictatorship is in some ways the most important property to be able to test.

We begin with a reminder: even though ${\mathcal D}$ is a subclass of the linear functions and we have a local tester for linearity, this doesn’t mean we automatically have a local tester for dictatorship. (This is in contrast to learning theory, where a learning algorithm for a concept class automatically works for any subclass.) The reason is that the non-dictator linear functions — i.e., $\chi_S$ for $|S| \neq 1$ — are at distance $\tfrac{1}{2}$ from ${\mathcal D}$ but are accepted by any linearity test with probability $1$.

Still, we could use a linearity test as a first component of a test for dictatorship; this essentially reduces the problem to testing if an unknown *linear* function is a dictator. Historically, the first local testers for dictatorship **[BGS95,PRS01]** worked this way; after testing linearity, they chose ${\boldsymbol{x}}, \boldsymbol{y} \sim \{0,1\}^n$ uniformly and independently, set $\boldsymbol{z} = {\boldsymbol{x}} \wedge \boldsymbol{y}$ (the bitwise logical AND), and tested whether $f(\boldsymbol{z}) = f({\boldsymbol{x}}) \wedge f(\boldsymbol{y})$. The idea is that the only parity functions which satisfy this “AND test” with probability $1$ are the dictators (and the constant $0$). The analysis of the test takes a bit of work; see the exercises for details.

Here we will describe a simpler dictatorship test. Recall we have already seen an important result which characterizes dictatorship: Arrow’s Theorem, from Chapter 2.5. Furthermore the robust version of Arrow’s Theorem (Corollary 2.59) involves evaluating a $3$-candidate Condorcet election under the impartial culture assumption, and this is the same as querying the election rule $f$ on $3$ correlated random inputs. This suggests a dictatorship testing component we call the “NAE Test”:

NAE TestGiven query access to $f : \{-1,1\}^n \to \{-1,1\}$:

- Choose ${\boldsymbol{x}}, \boldsymbol{y}, \boldsymbol{z} \in \{-1,1\}^n$ by letting each triple $({\boldsymbol{x}}_i, \boldsymbol{y}_i, \boldsymbol{z}_i)$ be drawn independently and uniformly at random from among the $6$ triples satisfying the not-all-equal predicate $\mathrm{NAE}_3 : \{-1,1\}^3 \to \{0,1\}$.
- Query $f$ at ${\boldsymbol{x}}$, $\boldsymbol{y}$, $\boldsymbol{z}$.
- Accept if $\mathrm{NAE}_3(f({\boldsymbol{x}}), f(\boldsymbol{y}), f(\boldsymbol{z}))$ is satisfied.

The NAE Test by itself is *almost* a $3$-query local tester for the property of being a dictator. Certainly if $f$ is a dictator then the NAE Test accepts with probability $1$. Furthermore, in Chapter 2.5 we proved:

Theorem 5 (Restatement of Corollary 2.58)If the NAE Test accepts $f$ with probability $1-\epsilon$ then $\mathbf{W}^{1}[f] \geq 1 – \frac92\epsilon$ and hence $f$ is $O(\epsilon)$-close to $\pm \chi_i$ for some $i \in [n]$ by the FKN Theorem.

There are two slightly unsatisfactory aspects to this theorem. First, it gives a local tester only for the property of being a dictator or a negated-dictator. Second, though the deduction $\mathbf{W}^{1}[f] \geq 1 – \frac92\epsilon$ requires only simple Fourier analysis, the conclusion that $f$ is close to a (negated-)dictator relies on the non-trivial FKN Theorem. Fortunately we can fix both issues simply by adding in the BLR Test:

Theorem 6Given query access to $f : \{-1,1\}^n \to \{-1,1\}$, perform both the BLR Test and the NAE Test. This is a $6$-query local tester for the property of being a dictator (with rejection rate $.1$).

*Proof:* The first condition in Definition 2 is easy to check: If $f : \{-1,1\}^n \to \{-1,1\}$ is a dictator then both tests accept $f$ with probability $1$. To check the second condition, fix $0 \leq \epsilon \leq 1$ and assume the overall test accepts $f$ with probability at least $1 – .1 \epsilon$. Our goal is to show that $f$ is $\epsilon$-close to some dictator.

Since the overall test accepts with probability at least $1-.1 \epsilon$, both the BLR and the NAE tests must individually accept $f$ with probability at least $1-.1\epsilon$. By the analysis of the NAE Test we deduce that $\mathbf{W}^{1}[f] \geq 1-\frac92 \cdot .1\epsilon = 1-.45\epsilon$. By the analysis of the BLR Test (Theorem 1.31) we deduce that $f$ is $.1\epsilon$-close to some parity function; i.e., $\widehat{f}(S^*) \geq 1-.2\epsilon$ for some $S^* \subseteq [n]$. Now if $|S^*| \neq 1$ we would have \[ 1 = \sum_{k=0}^n \mathbf{W}^{k}[f] \geq (1 – .45\epsilon) + (1-.2\epsilon)^2 \geq 2 – .85 \epsilon > 1, \] a contradiction. Thus we must have $|S^*| = 1$ and hence $f$ is $.1\epsilon$-close to the dictator $\chi_{S^*}$, stronger than what we need. $\Box$

As you can see, we haven’t been particularly careful about obtaining the largest possible rejection rate. Instead, we will be more interested in using as few queries as possible (while maintaining some positive constant rejection rate). Indeed we now show a small trick which lets us reduce our $6$-query local tester for dictatorship down to a $3$-query one. This is best possible since dictatorship can’t be locally tested with $2$ queries (see the exercises).

BLR+NAE TestGiven query access to $f : \{-1,1\}^n \to \{-1,1\}$:

- With probability $1/2$, perform the BLR Test on $f$.
- With probability $1/2$, perform the NAE Test on $f$.

Theorem 7The BLR+NAE Test is a $3$-query local tester for the property of being a dictator (with rejection rate $.05$).

*Proof:* The only observation we need to make is that if the BLR+NAE Test accepts with probability $1-.05\epsilon$ then both the BLR and the NAE tests individually must accept $f$ with probability at least $1-.1\epsilon$. The result then follows from the analysis of Theorem 6. $\Box$

Remark 8In general, this trick lets us take themaximumof the query complexities when we combine tests, rather than the sum (at the expense of worsening the rejection rate). Suppose we wish to combine $t = O(1)$ different testing algorithms, where the $i$th tester uses $r_i$ queries. We make an overall test which performs each subtest with probability $1/t$. This gives a $\max(r_1, \dots, r_t)$-query testing algorithm with the following guarantee: if the overall test accepts $f$ with probability $1-\frac{\lambda}{t} \epsilon $ theneverysubtest must accept $f$ with probability at least $1-\lambda\epsilon$.

We can now explain one reason why dictatorship is a particularly important property to be able to test locally. Given the BLR Test for linear functions it still took us a little thought to find a local test for the subclass ${\mathcal D}$ of dictators. But given our dictatorship test, it’s easy to give a $3$-query local tester for *any* subclass of ${\mathcal D}$. (On a related note, in the exercises you are asked to give a $3$-query local tester for any affine subspace of the linear functions.)

Theorem 9Let $\mathcal{S}$ be any subclass of $n$-bit dictators; i.e., let $S \subseteq [n]$ and let \[ \mathcal{S} = \{\chi_i : \{0,1\}^n \to \{0,1\} \mid i \in S\}. \] Then there is a $3$-query local tester for $\mathcal{S}$ (with rejection rate $.01$).

*Proof:* Let $1_S \in \{0,1\}^n$ denote the indicator string for the subset $S$. Given access to $f : \{0,1\}^n \to \{0,1\}$, the test is as follows:

- With probability $1/2$, perform the BLR+NAE Test on $f$.
- With probability $1/2$, apply the local correcting routine of Proposition 1.32 to $f$ on string $1_S$; accept if and only if the output value is $1$.

This test always makes either $2$ or $3$ queries, and whenever $f \in \mathcal{S}$ it accepts with probability $1$. Now let $0 \leq \epsilon \leq 1$ and suppose the test accepts $f$ with probability at least $1 – \lambda\epsilon$, where $\lambda = .01$. Our goal will be to show that $f$ is $\epsilon$-close to a dictator $\chi_i$ with $i \in S$.

Since the overall test accepts $f$ with probability at least $1-\lambda \epsilon$, the BLR+NAE Test must accept $f$ with probability at least $1-2\lambda\epsilon$. By Theorem 7 we may deduce that $f$ is $40\lambda\epsilon$-close to some dictator $\chi_i$. Our goal is to show that $i \in S$; this will complete the proof because $40\lambda\epsilon \leq \epsilon$ (by our choice of $\lambda = .01$).

So suppose by way of contradiction that $i \not \in S$; i.e., $\chi_i(1_S) = 0$. Since $f$ is $40\lambda\epsilon$-close to the parity function $\chi_i$, Proposition 1.32 tells us that \[ \mathop{\bf Pr}[\text{locally correcting $f$ on input $1_S$ produces the output $\chi_i(1_S) = 0$}] \geq 1 – 80\lambda\epsilon. \] On the other hand, since the overall test accepts $f$ with probability at least $1-\lambda \epsilon$, the second subtest must accept $f$ with probability at least $1-2\lambda\epsilon$. This means \[ \mathop{\bf Pr}[\text{locally correcting $f$ on input $1_S$ produces the output $0$}] \leq 2\lambda\epsilon. \] But this is a contradiction, since $2\lambda\epsilon < 1-80\lambda\epsilon$ for all $0 \leq \epsilon \leq 1$ (by our choice of $\lambda=.01$). Hence $i \in S$ as desired. $\Box$

Just a couple of really minor typos:

At the beginning of the proof of theorem 9 – I think you are missing a “the” – “Let $1_S$ denote indicator string for the subset $S$”

At the third paragraph above the definition of the BLR+NAE test – the comma is before the parenthesis

“(This is in contrast to learning theory, where a learning algorithm for a concept class automatically works for any subclass.)”

Thanks Tom! Actually, I didn’t understand what the typo was in the second part of your comment.

It’s probably just me being over-pedantic, but I think:

“works for any subclass.)”

should be:

“works for any subclass).”

Chicago Manual of Style, #6.96, “A period precedes the closing parenthesis if the entire sentence is in parentheses; otherwise it follows.”

Thanks though, keep the suggestions comment!

Sorry, my bad

After Remark 4, do you mean to say “by” in

“This is easier to achieve than satisfying by Definition 2″

?

Thanks, fixed.

While we’re on the topic of minor typos:

* just before Definition 1, “give encapsulate”

* this may be a matter of style, but I think “An r-query” rolls off the tongue easier than “A r-query”

Thanks, fixed both!

In the definition of the NAE Test, you might consider changing “drawn independent” to “drawn independent

ly“.You’re right, fixed! Thanks Amos.