New algorithms and lower bounds for monotonicity testing

Introduction

Monotonicity is a basic and natural property of functions. In the field of property testing, the problem of efficiently testing whether an unknown function is monotone has been the focus of a long and fruitful line of research, with many works (see e.g. [GGLR98, DGL+99, GGL+00, EKK+00, FLN+02, Fis04, BKR04, ACCL07, HK08, RS09, BBM12, BCGSM12, RRS+12, CS13a, CS13b, CS13c, BRY13]) studying this problem for functions with various domains and ranges.

Given as input a distance parameter $\varepsilon>0$ and oracle access to an unknown Boolean function $f:\{-1,1\}^{n}\to\{-1,1\}$, output Yes with probability at least $2/3$ if $f$ is monotone, and No with probability at least $2/3$ if $f$ is $\varepsilon$-far from monotone.

Our main contributions in this work are (i) a new lower bound that improves on the [FLN+02] lower bound by an exponential factor, and (ii) a new algorithm that improves on the [CS13a] upper bound (in terms of the dependence on $n$) by a polynomial factor. We now describe these contributions in more detail.

Our lower bound. We give an exponential improvement on the above-mentioned lower bounds of Fischer et al.:

There exists a universal constant $\varepsilon_{0}>0$ such that any non-adaptive algorithm for testing whether an unknown Boolean function is monotone versus $\varepsilon_{0}$-far from monotone must make $\Omega(n^{1/5}(\log n)^{-2/5})$ queries. Consequently, any adaptive algorithm must make $\Omega(\log n)$ queries.

While the aforementioned results of Fischer et al. represent the previous best lower bounds on the general testing problem as defined above, additional lower bounds are known for several restricted versions of the problem. In the same paper Fischer et al. gave an $\Omega(\sqrt{n})$ lower bound on the query complexity of any non-adaptive one-sided tester, i.e. one that always outputs Yes when $f$ is monotone (again, this directly implies an $\Omega(\log n)$ lower bound for adaptive one-sided testers). Restricting further, a pair tester is a non-adaptive one-sided tester that independently draws pairs of comparable points $x\prec y$ from some distribution and rejects if and only if some pair that is drawn violates monotonicity. Briët et al. [BCGSM12] proved an $\Omega(n/(\varepsilon\log n))$ lower bound on the query complexity of pair testers whose query complexity can be written as $q(n)/\varepsilon$ for some function $q.$

In addition to Theorem 1, we show that essentially the same lower bound holds for monotonicity testing of Boolean-valued functions over hypergrid domains $\{1,\dots,m\}^{n}$ for $m\geq 2.$ (Below and throughout this paper we write $[m]$ to denote $\{1,2,\dots,m\}$.) Our most general lower bound is the following:

Our algorithm. We present a new algorithm for monotonicity testing and prove the following result about its performance:

This work. Neither the [BO10] construction nor the [MORS09, RS13] construction can be used directly to establish a lower bound for monotonicity testing of functions $f:\{-1,1\}^{n}\to\{-1,1\}$; as described above, in the [BO10] construction both the $\mathcal{D}_{yes}$ and $\mathcal{D}_{no}$ functions are monotone, and in the [MORS09, RS13] construction a typical function from either distribution is far from monotone. Nevertheless, in this work we show that ingredients from [BO10, RS13] can be leveraged to obtain a polynomial lower bound for testing monotonicity of functions $f:\{-1,1\}^{n}\to\{-1,1\}$. Like these earlier works we employ Yao’s principle: we define a $\mathcal{D}_{yes}$ distribution that is supported on monotone LTFs, and a $\mathcal{D}_{no}$ distribution over LTFs that is almost entirely supported on LTFs that are constant-far from every monotone function, and use an analysis which is fairly similar to that of [BO10, RS13], to prove Theorem 1. Using the multidimensional Berry–Esséen theorem of [GOWZ10] to analyze our $\mathcal{D}_{yes}$ and $\mathcal{D}_{no}$ distributions would result in an $\Omega(n^{1/12})$ lower bound. To obtain our improved $\Omega(n^{1/5}\log^{-2/5}n)$ lower bound, we instead adapt a multidimensional CLT of Valiant and Valiant [VV11] (for Wasserstein distance) to our context.

2 The approach of our algorithm

Our algorithm builds on ingredients from [CS13a], so to explain our approach we first recall the necessary ingredients from that work. Fix a Boolean functionFor our algorithmic result it will be more convenient to view Boolean functions as mapping $\{0,1\}^{n}$ to $\{0,1\}$.$f:\{0,1\}^{n}\to\{0,1\}$, and let us say that a pair of inputs $(x,y)$ with $x\prec y$ is a violated edge if $f(x)=1,f(y)=0$ and $(x,y)$ is an edge in $\{0,1\}^{n}$ (i.e. the Hamming distance between them is 1). [CS13a] establishes a very useful “dichotomy theorem” about Boolean functions $f:\{0,1\}^{n}\to\{0,1\}$ that are $\varepsilon$-far from monotone: for any $s>0$, any such function either must have $\Omega(\varepsilon s2^{n})$ violated edges, or must have a matching (i.e. a vertex-disjoint set) of $\Omega(\varepsilon 2^{n}/s)$ violated edges.

3 Preliminaries

We will need a few standard facts from probability theory:

Let $\mathcal{G}$ be a Gaussian with mean 0 and variance $\sigma^{2}$. Then for all $0<a<1$ it holds that \operatorname{{\bf Pr}}\big{[}\mathcal{G}\in[0,a\sigma]\big{]}=\Omega(a).

For all $c>0$ there exists an $\varepsilon=\varepsilon(c)\in(0,1]$ such that the following holds. For all even (resp. odd) $n$,

For $i\in[n]$, the influence of coordinate $i$ on $f$, denoted $\mathbf{Inf}_{i}[f]$, is the probability

where $\boldsymbol{x}^{\oplus i}$ denotes the string $\boldsymbol{x}$ with its $i$-th coordinate flipped. The following fact relates the influences of an LTF to its degree-$1$ Fourier coefficients:

The lower bound: Proof of Theorem 2

Let $\mathcal{T}$ be any deterministic non-adaptive two-sided $q$-query algorithm for testing whether a black-box Boolean function $f:\{-1,1\}^{n}\to\{-1,1\}$ is monotone. Then

We prove Proposition 2.1 in Section 2.1, followed by Proposition 2.2 in Section 2.2.

Since $\mathbf{Inf}_{i}[f]=\Omega(1/\sqrt{n})$ for all $i\in[m]$, by Fact 1.5 we have that $\widehat{f}(i)=-\Omega(1/\sqrt{n})$ for all $i\in[m]$. Hence for all monotone Boolean functions $g$, we have

Here the second equality is by Parvseval’s identity; the penultimate equality uses the fact that $\widehat{g}(i)\geq 0$ for all $i\in[n]$, which in turn holds since $g$ is a monotone Boolean function. This completes the proof of Proposition 2.1.

2 Proof of Proposition 2.2

We will need the following multidimensional Berry–Esséen theorem, the proof of which we defer to Section 3.

We begin by writing $\mathbf{S}=\mathbf{X}^{(1)}+\cdots+\mathbf{X}^{(n)}$, where $\mathbf{X}^{(j)}=\boldsymbol{\sigma}_{j}\cdot Q_{*j}$ and $\boldsymbol{\sigma}_{j}$ is uniform over $\{1,3\}$; i.e. each $\mathbf{X}^{(j)}$ is independently $Q_{*j}$ with probability $1/2$ and $3\cdot Q_{*j}$ with probability $1/2$. Likewise we may express $\mathbf{T}=\mathbf{Y}^{(1)}+\cdots+\mathbf{Y}^{(n)}$, where $\mathbf{Y}^{(j)}=\boldsymbol{\nu}_{j}\cdot Q_{*j}$ and $\boldsymbol{\nu}_{j}$ is $-1$ with probability $1/10$ and $7/3$ with probability $9/10$. We claim that the $\mathbf{X}^{(j)}$’s and $\mathbf{Y}^{(j)}$’s have matching means and covariance matrices; it suffices to check this for $\mathbf{X}^{(1)}$ and $\mathbf{Y}^{(1)}$. For means, we see that indeed

As for the covariance matrices, we let $i_{1},i_{2}\in[q]$ and calculate

Similarly, the corresponding entry of $\operatorname{{\bf Cov}}[\mathbf{Y}^{(1)}]$ is:

Since the $\mathbf{X}^{(j)}$’s and $\mathbf{Y}^{(j)}$’s have matching means and covariance matrices, so do their sums $\mathbf{S}$ and $\mathbf{T}$, and so Theorem 5 gives a bound on the differences $|\operatorname{{\bf Pr}}[\mathbf{S}\in\mathcal{O}]-\operatorname{{\bf Pr}}[\mathcal{G}\in\mathcal{O}]|$ and $|\operatorname{{\bf Pr}}[\mathbf{T}\in\mathcal{O}]-\operatorname{{\bf Pr}}[\mathcal{G}\in\mathcal{O}]|$ for the same $q$-dimensional Gaussian $\mathcal{G}$. Recalling that $\mathbf{X}^{(j)}_{i}=\boldsymbol{\sigma}_{j}\cdot Q_{i,j}$ where $Q_{i,j}\in\{-1,1\}^{n}$, we have that $\operatorname{{\bf Var}}[\mathbf{X}_{i}^{(j)}]=1$, and likewise $\operatorname{{\bf Var}}[\mathbf{Y}^{(j)}_{i}]=1$. Therefore, two applications of Theorem 5 with $\tau:=O(1)$ along with the triangle inequality yields the bound

for all $r>0$. Choosing $r:=(qn)^{1/4}(\log n)^{1/2}$ completes the proof. ∎

Multidimensional Berry–Esséen via the Valiant–Valiant CLT

In this section we prove Theorem 5 by adapting a recent multidimensional CLT of Valiant and Valiant [VV11] which bounds the Wasserstein distance between a sum of independent vector-valued random variables and a multidimensional Gaussian.

Valiant and Valiant [VV11] recently used Stein’s method to prove the following central limit theorem for Wasserstein distance:

where $\mathcal{G}$ is the $q$-dimensional Gaussian with the same mean and covariance matrix as $\mathbf{S}$.

to be the radius-$r$ region around the orthant boundaries, and partition $\mathcal{O}$ into $\mathcal{O}_{bd}:=\mathcal{O}\cap W_{r}$ (the points in $\mathcal{O}$ that lie close to the orthant boundaries) and $\mathcal{O}_{in}:=\mathcal{O}\setminus W_{r}$ (the points that lie far away from the orthant boundaries). We have

We bound the quantities $\Delta$ and $\Gamma$ separately. For $\Gamma$, we have that

where (3) is a union bound over all $q$ dimensions, and (4) uses Fact 1.1 (Gaussian anti-concentration), the fact that $\mathcal{G}_{i}$ is a Gaussian with variance \sum_{j=1}^{n}\operatorname{{\bf Var}}\big{[}\mathbf{X}^{(j)}_{i}\big{]}, and Theorem 4 (Berry–Esséen).

Note that $\Delta_{\text{\it near}}(\mathcal{D})$ and $\Delta_{\text{\it far}}(\mathcal{D})$ sum to the quantity on the left-hand side of (5), and so $\Delta_{\text{\it near}}(\mathcal{D})+\Delta_{\text{\it far}}(\mathcal{D})\geq\Delta$. (In words, since $\mathbf{S}$ places $\Delta$ more mass on $\mathcal{O}_{in}$ than $\mathcal{G}$ does, any scheme $\mathcal{D}$ of moving the mass of $\mathbf{S}$ to obtain $\mathcal{G}$ must move at least $\Delta$ amount from within $\mathcal{O}_{in}$ to outside it. $\Delta_{\text{\it near}}(\mathcal{D})$ is the amount moved from within $\mathcal{O}_{in}$ to $\mathcal{O}$’s boundary $\mathcal{O}_{bd}$, and $\Delta_{\text{\it far}}(\mathcal{D})$ is the rest, moved from within $\mathcal{O}_{in}$ to locations entirely out of $\mathcal{O}$.) Since $\|u-v\|_{2}\geq r$ for any pair of points $u\in\mathcal{O}_{in}$ and $y\notin\mathcal{O}$, it follows that

We consider two cases, depending on the relative magnitudes of $\Delta_{\text{\it near}}(\mathcal{D})$ and $\Delta_{\text{\it far}}(\mathcal{D})$. If $\Delta_{\text{\it far}}(\mathcal{D})\geq\Delta_{\text{\it near}}(\mathcal{D})$, we first observe that for all $j\in[n]$ we have \big{\|}\mathbf{X}^{(j)}-\operatorname{{\bf E}}\big{[}\mathbf{X}^{(j)}\big{]}\big{\|}_{2}\leq\tau\sqrt{q} with probability $1$, since each of its $q$ coordinates $i$ satisfies \big{|}\mathbf{X}^{(j)}_{i}-\operatorname{{\bf E}}\big{[}\mathbf{X}^{(j)}_{i}\big{]}\big{|}\leq\tau with probability $1$ by the assumption of the theorem. Therefore we may apply Theorem 7 (Valiant–Valiant CLT) with $\beta:=\tau\sqrt{q}$ to get

and hence $\Delta=O((\tau q^{3/2}\log n)/r)$, which along with our upper bound on $\Gamma$ completes the proof. If on the other hand $\Delta_{\text{\it near}}(\mathcal{D})>\Delta_{\text{\it far}}(\mathcal{D})$, then

and again our bound on $\Gamma$ completes the proof. ∎

A lower bound for general hypergrid domains

We prove Theorem 2 via a reduction to the $m=2$ case (i.e. Theorem 1). The reduction is simpler for even $m$ so for ease of exposition we assume below that $m$ is even. In this case Theorem 2 is a direct consequence of Theorem 1 and the following proposition:

defined by (6) below satisfies the following two properties:

If $f:\{-1,1\}^{n}\to\{-1,1\}$ is monotone then $\Phi[f]$ is monotone as well.

If $f:\{-1,1\}^{n}\to\{-1,1\}$ is $\varepsilon$-far from monotone then $\Phi[f]$ is $\varepsilon$-far from monotone as well.

We will need the following characterization of distance to monotonicity.

For all $f:[m]^{n}\to\{-1,1\}$ and $\varepsilon>0$, we have that $f$ is $\varepsilon$-far from monotone if and only if there exists $\varepsilon m^{n}$ many pairwise disjoint ordered pairs of vertices $(x^{i},y^{i})\in[m]^{n}\times[m]^{n}$ such that $x^{i}\prec y^{i}$ and $f(x^{i})>f(y^{i})$. We will call each such pair a violation with respect to $f$.

For every $f:\{-1,1\}^{n}\to\{-1,1\}$, we define $\Phi[f]:[m]^{n}\to\{-1,1\}$ to be the function

where we use ${\bf 1}[\cdot]$ to denote the $\{\pm 1\}$-valued indicator where ${\bf 1}[P]=1$ if $P$ is true, and $-1$ otherwise. (Note that $m/2$ is an integer by our assumption that $m$ is even.)

It is straightforward to verify that $\Phi[f]$ is monotone if $f$ is monotone, and so it remains to show that $\Phi[f]$ is $\varepsilon$-far from monotone if $f$ is $\varepsilon$-far from monotone. Since $f$ is $\varepsilon$-far from monotone, we have by Theorem 8 that there exist $\varepsilon 2^{n}$ many pairwise disjoint pairs $(x^{i},y^{i})\in\{-1,1\}^{n}\times\{-1,1\}^{n}$ that are violations with respect to $f$; we will exhibit $\varepsilon m^{n}$ many pairwise disjoint pairs in $[m]^{n}$ that are violations with respect to $\Phi[f]$, which along with another application of Theorem 8 completes the proof. Let S:\{-1,1\}\to\big{\{}[m/2],\{(m/2)+1,\ldots,m\}\big{\}} be the set-valued function

and by a slight abuse of notation, we also define

to be a function that maps points $x\in\{-1,1\}^{n}$ to subsets of $[m]^{n}$. Note that $|S(x)|=(m/2)^{n}$ for all $x\in\{-1,1\}^{n}$, and $S(x)\cap S(y)=\emptyset$ if $x\neq y$. Furthermore, $\Phi[f](x^{\prime})=f(x)$ for all $x\in\{-1,1\}^{n}$ and $x^{\prime}\in S(x)$. In words, $S$ maps each $1$-input of $f$ to a set of $(m/2)^{n}$ many $1$-inputs of $\Phi[f]$, and likewise each -input of $f$ to a set of $(m/2)^{n}$ many -inputs of $\Phi[f]$.

For any pair $(x,y)\in\{-1,1\}^{n}\times\{-1,1\}^{n}$ that is a violation with respect to $f$, consider pairing the $(m/2)^{n}$ elements of $S(x)$ with the $(m/2)^{n}$ elements of $S(y)$ in the obvious way (i.e. each $a=(a_{1},\dots,a_{n})\in S(x)$ is is paired with the unique element $b=(b_{1},\dots,b_{n})\in S(y)$ that has $(a_{i}\mod m/2)=(b_{i}\mod m/2)$ for all $i$). Since $x\prec y$, it follows from the definition of $S$ that every $x^{\prime}\in S(x)$ is paired with $y^{\prime}\in S(y)$ where $x^{\prime}\prec y^{\prime}$. Furthermore, as noted above $\Phi[f](x^{\prime})=f(x)=1$ whereas $\Phi[f](y^{\prime})=f(y)=0$, and so every pair $(x^{\prime},y^{\prime})\in S(x)\times S(y)$ is a violation with respect to $\Phi[f]$. Therefore each of the $\varepsilon 2^{n}$ many pairs $(x,y)\in\{-1,1\}^{n}\times\{-1,1\}^{n}$ that are violations with respect to $f$ gives rise to $(m/2)^{n}$ many pairwise disjoint pairs $(x^{\prime},y^{\prime})\in S(x)\times S(y)$ that are violations with respect to $\Phi[f]$. Finally recalling that $S(x)\cap S(y)=\emptyset$ if $x\neq y$, we conclude that there are indeed $\varepsilon 2^{n}\cdot(m/2)^{n}=\varepsilon m^{n}$ many pairwise disjoint pairs that are violations with respect to $\Phi[f]$. This finishes the proof. ∎

The algorithm

Throughout the proof of our upper bound we will assume that $1/n\leq\varepsilon\leq 1/2.$ Note that this is without loss of generality, since if $\varepsilon<1/n$ then the edge tester alone succeeds with probability $\Omega(\varepsilon/n)=\Omega(\varepsilon^{2})$, and if $\varepsilon>1/2$ then every $f$ is $\varepsilon$-close to one of the two constant functions, both of which are monotone.

and will denote $d(n,\varepsilon)$ simply by $d$ when the distance parameter $\varepsilon$ is clear from the context. For each $i\in\{0,1,\ldots,n\}$ we let $L_{i}:=\{x\in\{0,1\}^{n}\colon\|x\|_{1}=i\}$ denote the $i$-th layer, and refer to

First pick a path $\boldsymbol{p}$ uniformly from the collection of all paths going from $0^{n}$ to $1^{n}$.

This distribution is a slight variant of the one induced by the [CS13a] path tester, which takes a parameter $\sigma$ as input and disallows pairs $(x,y)$ for which $\|x-y\|_{1}$ is too small relative to $\sigma$. Our new tester will not sample from $\mathcal{D}$ (see Section 5.3), but we will use $\mathcal{D}$ in our analysis. We remark here that $\boldsymbol{x}=\boldsymbol{y}$ with positive probability under $\mathcal{D}$.

If $\boldsymbol{x},\boldsymbol{y}$ were chosen independently and uniformly from $\{0,1\}^{n}$, then the probability that they both land in a fixed set $A$ of $\sigma 2^{n}$ points, for some $\sigma\in(0,1)$, would be $\sigma^{2}$. The following lemma states that the probability is not much lower for a pair drawn from $\mathcal{D}$:

and so it suffices to lower bound $\mathop{{\bf E}\/}_{\boldsymbol{p}}[|\boldsymbol{p}_{\text{mid}}\cap A|]$ by $\Omega(\sigma\sqrt{n})$. This is exactly Claim 2.2.1 of [CS13a]; we repeat the calculation here for the sake of completeness:

where we use ${\bf 1}[\cdot]$ to denote the $\{0,1\}$-valued indicator where ${\bf 1}[P]=1$ if $P$ is true, and otherwise. Here (7) uses the fact that a uniformly random path $\boldsymbol{p}$ from $0^{n}$ to $1^{n}$ contains a uniformly random point in layer $L_{i}$, and (8) holds since $|L_{i}|\leq 2^{n}/\sqrt{n}$ for all $i$. ∎

We will need a numerical lemma concerning the ratio of binomial coefficients.

Let $\varepsilon\geq 1/n$, and $a,b\in[(n-d)/2,(n+d)/2]$ be integers where $a>b$. Then

We prove the first equation and the second equation is similar. By a routine calculation we verify that the first ratio is maximized when $a=(n+d)/2$ and $b=n/2$, and so

Then pick a path $\boldsymbol{p}$ uniformly from the collection of all paths going through $0^{n}$, $\boldsymbol{x}$, and $1^{n}$.

We get the following corollary from Lemmas 5.1 and 5.2:

As a result, we have for every comparable pair $(x,y)$ in the middle layers

2 Density and score

We need the following definition to give a more detailed analysis on the consequence of Corollary 5.3, which is key to the analysis of our monotonicity tester described in Section 5.3.

Let $A\subseteq\{0,1\}^{n}$. For all $x\in\{0,1\}^{n}$ and $k\in\{0,1,\ldots,n\}$, we define the following quantities:

The following lemma relates the distribution $\mathcal{D}^{\prime}$ (more precisely, the distribution over $\boldsymbol{y}$ that is induced by conditioning on a particular outcome of $\boldsymbol{x}$) to the notion of score:

We use the previous two lemmas to lower bound the expected downward $A$-score of an $\boldsymbol{x}$ drawn uniformly at random from $A$:

where the final equality holds by the first part of Lemma 5.2. This proves (9), which together with Lemma 5.4 gives

On the other hand, by Corollary 5.3 we have

Combining (10) with (11) and rearranging completes the proof. ∎

Lemma 5.5 lower bounds the average downward $A$-score of points $x\in A$; its conclusion may be equivalently rewritten as the following sum:

This follows from (12), (13), and the fact that there are only $m+1$ many buckets. ∎

Let $\varepsilon\geq 1/n$ and $M$ be a matching of $\sigma 2^{n}$ edges in the middle layers. Let

Next for every edge $(x,y)\in M$ we have that

3 The weighted path tester and its analysis

Given a Boolean function $f$, recall that a pair $(x,y)$ of vertices is a violated pair with respect to $f$ if $x\prec y$ and $f(x)>f(y)$. Our algorithm weighted-path-tester for monotonicity testing proceeds as follows:

Pick a path $\boldsymbol{p}$ uniformly from the collection of all paths going through $0^{n},\boldsymbol{y}$ and $1^{n}$, and set $\boldsymbol{x}$ to be the (unique) point on $\boldsymbol{p}$ that has $\boldsymbol{x}\prec\boldsymbol{y}$ and $\|\boldsymbol{x}-\boldsymbol{y}\|_{1}=k.$

Reject iff $(\boldsymbol{x},\boldsymbol{y})$ is a violated pair.

We note that an equivalent formulation of step (4) is that $\boldsymbol{x}$ is drawn uniformly from \big{\{}z\in\{0,1\}^{n}\colon\text{z\prec\boldsymbol{y}$and$\|\boldsymbol{y}-z\|_{1}=\boldsymbol{k}}\big{\}}. Below we show that if there is a $(\sigma 2^{n})$-sized matching $M$ of violated edges of $f$ in the middle layers of the hypercube, then the tester above succeeds in finding a violated pair with probability roughly $\Omega(\sigma^{2}/\sqrt{n})$.

Let $f:\{0,1\}^{n}\to\{0,1\}$ and $\varepsilon\geq 1/n$. Suppose there is a $(\sigma 2^{n})$-sized matching $M$ of violated edges of $f$ all lying in the middle layers of the hypercube. Then weighted-path-tester succeeds (i.e. samples $\boldsymbol{x}$ and $\boldsymbol{y}$ that form a violated pair with respect to $f$) with probability

4 Proof of Theorem 3

Finally we combine Proposition 5.8 with the dichotomy theorem of [CS13a] to prove Theorem 3. To state the latter, we let $v2^{n}$ denote the total number of violated edges in $f$. We also let $\sigma 2^{n}$ denote the size of the largest matching of violated edges in the middle layers. Then we have

For any $f$ that is $\varepsilon$-far from monotone, $v\cdot\sigma=\Omega(\varepsilon^{2})$.

As mentioned at the beginning of Section 5, we may assume without loss of generality that $\varepsilon\geq 1/n$ since otherwise the edge tester alone succeeds with probability $\Omega(\varepsilon/n)=\Omega(\varepsilon^{2})$. When $\varepsilon\geq 1/n$, our tester flips a coin, runs the edge tester with probability $1/2$, and runs weighted-path-tester with probability $1/2$. Given $v$ and $\sigma$ as defined above, the success probability of the edge tester is $\Omega(v/n)$; the success probability of weighted-path-tester is given in (16). It follows from Theorem 11 that the average of these two is at least

Acknowledgements

We thank Eric Blais for a helpful discussion that led to an improvement of our lower bound for general hypergrid domains.

References

The monotonicity of $h$ is straightforward to verify, as is the fact that $|\{x\in[m]^{k}\colon h(x)=1\}|=|\{x\in[m]^{k}\colon h(x)=-1\}|+1$. The proof is complete by noticing that the mapping

is a bijection between $h^{-1}(-1)$ and $h^{-1}(1)\setminus\{\lceil m/2\rceil^{k}\}$. ∎

With Lemma A.1 in hand we are ready to prove the following analogue of Proposition 4.1 for hypergrid domains $[m]^{n}$ when $m$ is odd. Given the monotone function $h$ defined in Lemma A.1, let $h^{\prime}:[m]^{k}\to\{-1,1,\bot\}$ be the partial function where $h^{\prime}(x)=\bot$ if $x=\lceil m/2\rceil^{k}$, and $h^{\prime}(x)=h(x)$ otherwise (and so $|\{x\in[m]^{k}\colon h(x)=1\}|=|\{x\in[m]^{k}\colon h(x)=-1\}|=(m^{k}-1)/2$).

defined by (17) below satisfies the following two properties:

If $f:\{-1,1\}^{n}\to\{-1,1\}$ is monotone then $\Phi[f]$ is monotone as well.

If $f:\{-1,1\}^{n}\to\{-1,1\}$ is $\varepsilon$-far from monotone then $\Phi[f]$ is $\Omega(\varepsilon)$-far from monotone.

Fix $k:=\lceil\log n\rceil$. For every $f:\{-1,1\}^{n}\to\{-1,1\}$, we define $\Phi[f]:[m]^{kn}\to\{-1,1\}$ to be the following function: for all $x^{1},\ldots,x^{n}\in[m]^{k}$

Since $h$ is monotone it follows that $\Phi[f]$ is monotone if $f$ is monotone, and so it remains to show that $\Phi[f]$ is $\Omega(\varepsilon)$-far from monotone if $f$ is $\varepsilon$-far from monotone. Since $f$ is $\varepsilon$-far from monotone, we have by Theorem 8 that there exist $\varepsilon 2^{n}$ many pairwise disjoint pairs $(x^{i},y^{i})\in\{-1,1\}^{n}\times\{-1,1\}^{n}$ that are violations with respect to $f$; we will exhibit $\Omega(\varepsilon\,m^{kn})$ many pairwise disjoint pairs in $[m]^{kn}$ that are violations with respect to $\Phi[f]$, which along with another application of Theorem 8 completes the proof.

Using the same notation as in the proof of Proposition 4.1, we define the set-valued function $S$ mapping $x\in\{-1,1\}^{n}$ to subsets of $[m]^{kn}$ as follows:

for all $x\in\{-1,1\}^{n}$ (where we have used our choice of $k=\lceil\log n\rceil$ for the inequality), and $S(x)\cap S(y)=\emptyset$ if $x\neq y$. Furthermore, $\Phi[f](x^{\prime})=f(x)$ for all $x\in\{-1,1\}^{n}$ and $x^{\prime}\in S(x)$. In words, $S$ maps each $1$-input of $f$ to a set of $((m^{k}-1)/2)^{n}$ many $1$-inputs of $\Phi[f]$, and likewise each -input of $f$ to a set of $((m^{k}-1)/2)^{n}$ many -inputs of $\Phi[f]$.

For any pair $(x,y)\in\{-1,1\}^{n}\times\{-1,1\}^{n}$, $x\prec y$, that is a violation with respect to $f$, consider pairing the $((m^{k}-1)/2)^{n}$ elements of $S(x)$ with the $((m^{k}-1)/2)^{n}$ elements of $S(y)$ via $\Psi$ from Lemma A.1 as follows: each $a\in S(x)$, which we will view as $a=(a_{1},\ldots,a_{n})\in([m]^{k})^{n}$, is paired with the unique element $b=(b_{1},\dots,b_{n})\in S(y)$ where $b_{i}=a_{i}$ if $x_{i}=y_{i}$, and $b_{i}=\Psi(a_{i})$ if $x_{i}<y_{i}$. Since $x\prec y$, it follows from the definitions of $S$ and $\Psi$ that every $x^{\prime}\in S(x)$ is paired with $y^{\prime}\in S(y)$ where $x^{\prime}\prec y^{\prime}$. Furthermore, as noted above $\Phi[f](x^{\prime})=f(x)=1$ whereas $\Phi[f](y^{\prime})=f(y)=0$, and so every pair $(x^{\prime},y^{\prime})\in S(x)\times S(y)$ is a violation with respect to $\Phi[f]$. Therefore each of the $\varepsilon 2^{n}$ many pairs $(x,y)\in\{-1,1\}^{n}\times\{-1,1\}^{n}$ that are violations with respect to $f$ gives rise to $\Omega(m^{kn}/2^{n})$ many pairwise disjoint pairs $(x^{\prime},y^{\prime})\in S(x)\times S(y)$ that are violations with respect to $\Phi[f]$. Finally recalling that $S(x)\cap S(y)=\emptyset$ if $x\neq y$, we conclude that there are indeed $\varepsilon 2^{n}\cdot\Omega(m^{kn}/2^{n})=\Omega(\varepsilon\,m^{kn})$ many pairwise disjoint pairs that are violations with respect to $\Phi[f]$. This finishes the proof. ∎