§7.1: Dictator testing

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 1 An $r$-query function testing algorithm for 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 2 Let $\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 a local tester for $\mathcal{C}$ (with rejection 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 3 By 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 4 To 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 natural families of 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 Test Given 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 6 Given 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 Test Given 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 7 The 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 8 In general, this trick lets us take the maximum of 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 $ then every subtest 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 9 Let $\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$

11 comments to §7.1: Dictator testing

Leave a Reply

  

  

  

You can use most standard LaTeX, as well as these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>