Adaptive Lower Bound for Testing Monotonicity on the Line
Aleksandrs Belovs
cs.CC cs.DS

Oceanic tides from Earth-like to ocean planets
    P. Auclair-Desrotour1,2,4
     S. Mathis2,3J. Laskar1
     J. Leconte4
          
    Received ...; accepted ...
=====================================================================================


In the property testing model, the task is to distinguish objects possessing some property from the objects that are far from it.
One of such properties is monotonicity, when the objects are functions from one poset to another.  This is an active area of research.
In this paper we study query complexity of -testing monotonicity of a function f [n]→[r].  All our lower bounds are for adaptive two-sided testers.


  * We prove a nearly tight lower bound for this problem in terms of r.  The bound is Ω[log r/loglog r] when = 1/2.
No previous satisfactory lower bound in terms of r was known.

  * We completely characterise query complexity of this problem in terms of n for smaller values of .  The complexity is Θ[^-1log ( n)].  
Apart from giving the lower bound, this improves on the best known upper bound.


Finally, we give an alternative proof of the Ω(^-1dlog n - ^-1log^-1) lower bound for testing monotonicity on the hypergrid [n]^d due to Chakrabarty and Seshadhri (RANDOM'13).





§ INTRODUCTION


The framework of property testing was formulated by Rubinfeld and Sudan <cit.> and Goldreich  <cit.>.
A property testing problem is specified by a property , which is a class of functions mapping some finite set D into some finite set R, and proximity parameter , which is a real number between 0 and 1.
An -tester is a bounded-error randomised query algorithm which, given oracle access to a function f D→ R, distinguishes between the case when f belongs to  and the case when f is -far from .
The latter means that any function g∈ differs from f on at least  fraction of the points in the domain D.
The usual complexity measure is the number of queries to the function f.
A tester is with 1-sided error if it always accepts a function f in .
A tester is non-adaptive if its queries do not depend on the responses received to the previous queries.
The most general tester is adaptive with 2-sided error, which we will implicitly assume in this paper.

When both the domain D and the range R are partially ordered sets, a natural property to consider is that of monotonicity.
A function f D→ R is called monotone if x≤ y implies f(x)≤ f(y) for all x,y∈ D.
Usually it is assumed that R is a totally ordered set.
In this case, the property  consists of all monotone functions from D to R. 
The problem of testing monotonicity was explicitly formulated and studied by Goldreich  <cit.> in the case when D is the Boolean hypercube {0,1}^d and R=.
This is an active area of research as exemplified by the papers <cit.>.

However, slightly earlier than Goldreich , Ergün studied the same problem for functions f [n]→[r].  Ergün called it spot-checker for sorting, but now this problem is generally known as monotonicity testing on the line, the line being the totally ordered set [n].
This problem is the main focus of this paper.
Although this problem is arguably simpler than testing monotonicity on the hypercube, it seems more natural and important from the practical point of view.
Ergün mention that their algorithm can be used in software quality assurance by providing a very fast verification procedure that checks whether a presumably sorted array is indeed sorted.

A related problem is that of testing monotonicity on the hypergrid.
A hypergrid is a set [n]^d of d-tuples with elements in [n].  For two d-tuples x = (x_1,…,x_d) and y = (y_1,…,y_d), we have x≤ y iff x_i≤ y_i for all i.  We are interested in functions from [n]^d to [r] for some positive integers n,d and r.
Clearly, this is a generalisation of both monotonicity testing on the line (when d=1) and on the hypercube (when n=2).
These problems are closely related, so it is important to consider all of them when discussing prior work.



  
Prior work.
We proceed with a brief discussion of previous results related to our paper.
Let us start with the upper bounds.
As mentioned above, the problem of testing monotonicity on the line was first considered by Ergün  <cit.>, who gave an -tester with complexity O[^-1log n].
Concerning the case of functions from the hypercube {0,1}^d to arbitrary [r], Goldreich  <cit.> proposed the edge tester, and Chakrabarty and Seshadhri <cit.> proved that it has query complexity O(d/).
In the latter paper, an -tester for testing monotonicity on the hypergrid [n]^d with complexity O(^-1dlog n) was also constructed.

Now let us turn to the lower bounds.
Ergün  <cit.> proved a lower bound
[If a lower bound does not state dependence on , it is assumed that the lower bound holds for some choice of =Ω(1).]
of Ω(log n) for testing monotonicity on the line in the so-called comparison-based model.
In this model, each query of the tester may depend only on the order relations between the responses to the previous queries, but not on the values of the responses themselves.[
Note that this does not mean that the tester asks queries of the form f(x)?≤f(y).  The query is still an input x, and the tester learns about the order relations between f(x) and f(y) for all previously queried y's.
]
Fischer <cit.> proved that any lower bound for a monotonicity testing problem in the comparison-based model implies the same lower bound in the usual value-based model.
This immediately gives an Ω(log n) lower bound for testing monotonicity on the line, matching the upper bound by Ergün  <cit.>.
Chakrabarty and Seshadhri <cit.> used the same technique to prove a lower bound of Ω(^-1dlog n - ^-1log^-1) for testing monotonicity on hypergrids.
Unfortunately, Fischer's construction is based on Ramsey theory, which means that, in order for this construction to work, the size of the range, r, has to be really huge.

Large values of r in the above lower bounds may lead one to study complexity of testing monotonicity with respect to the size of the range, r, rather than the size of the domain, n.
Moreover, there are two parameters related to the output of the function f: the size of the range (codomain) r, and the size of the image t = |f([n])|: the number of different values attained by the function.
Clearly, t≤ r.
This means it is more interesting to prove upper bounds in terms of t and lower bounds in terms of r.

Let us start with the upper bounds.
First, it is easy to see that if r=2, then O(1/) queries suffice to -test monotonicity on the line.
Generalising this observation, Pallavoor  <cit.> constructed an -tester for monotonicity on the line with complexity O(1/log t) for general t, as well as an -tester for monotonicity on hypergrids with complexity O[d/logd/log t].
Since t≤ n, the lower bound of Ω(log n) due to Fischer <cit.> implies the lower bound of Ω(log t) for all n≥ t and r large enough.
[
The size of the domain of a function f [n]→[r] can be inflated without changing its distance to monotonicity by replacing f with the function f' [nk]→[r] given by f'(x) = f([x/k]).
]

The main prior technique capable of proving strong lower bounds for functions with small range is that of communication complexity.
Blais introduced this technique in <cit.>, where it was proven that Ω[min{d, r^2}] queries are required to test a function f{0,1}^d→[r] for monotonicity.
In a subsequent paper <cit.> a non-adaptive lower bound of Ω(dlog n) was proven for functions f [n]^d→[nd] on the hypergrid.
In the special case of d=1, this gives a lower bound of Ω[logmin{n,r}] for testing monotonicity of a function f [n]→[r] on the line.





  
Our results.
Our main contribution is an adaptive lower bound for testing monotonicity on the line.  In order not to obstruct our main argument, we first prove the bound for = Ω(1), and then show how to adapt the construction for smaller values of . 


Every adaptive bounded-error 1/2-tester for monotonicity of a function f [2^k]→ [k^3k] has query complexity Ω(k).


Unlike <cit.>, we bypass Ramsey theory and construct two explicit distributions of functions that are hard to distinguish by an adaptive algorithm.
In terms of the size of the domain, n, this gives the same lower bound of Ω(log n) as in Fischer's paper <cit.>, but with vastly reduced range size.
A more direct construction can be beneficial for generalisation to other models, like quantum testers, since it is not known how to adapt Fischer's technique to the quantum settings.

In terms of the size of the range, r, this gives a lower bound of of Ω[log r/loglog r], thus nearly matching the upper bound by Pallavoor  <cit.>.
Finally, we get a slightly worse estimate (in terms of the range size) than that of Blais  <cit.> but for adaptive testers.
We prove thm:main in sec:main.

In sec:smallEpsilon, we consider the case of general .
First, we show that the construction of thm:main can be used to prove an Ω[^-1log ( n)] lower bound for -testing monotonicity on the line.
For large values of , this matches the upper bound of O[^-1log n] due to Ergün  <cit.>, but is slightly worse when  is close to 1/n.
However, we manage to improve the algorithm and prove an upper bound of O[^-1log ( n)] for all n≥ 2, thus matching our lower bound.
If n < 2, the complexity is obviously Θ(n), hence, this completely resolves the problem of -testing monotonicity on the line for all values of n and ≤ 1/2.

Finally, in sec:hypergrid, we show how our construction can be adapted to prove the lower bound Ω(^-1dlog n - ^-1log^-1) for -testing monotonicity on the hypergrid [n]^d.
This coincides with the bound by Chakrabarty and Seshadhri <cit.>, but, again, our construction bypasses Ramsey theory, which results in a vastly reduced range size.





§ PRELIMINARIES

Although this is not standard, it will be convenient for us to denote [n]={0,1,…,n-1}, and [a..b]={a,a+1,…,b-1}.
Thus, [n] = [0..n], and note that [a..b] does not contain b.

An assignment α S→ [r] is a function defined on a subset S⊆[n].  
The weight of α is the size of S.
We say that f agrees with α if f(x)=α(x) for all x∈ S.
This is notated by f⇁α.
The choice of notation is to distinguish it from f∼μ which means that f is distributed according to the probability distribution μ.

All logarithms are to the base of 2.




§ PROOF OF THM:MAIN



We will define a probability distribution μ on monotone functions f [2^k]→ [k^3k] and a probability distribution ν on functions g [2^k]→ [k^3k] that are 1/2-far from monotone.
It will be impossible to distinguish these two distributions using fewer than Ω(k) queries.
Let m=k^3, so that r=m^k.

We define the distribution μ in two different but equivalent ways.
First, μ is defined as the last member in an inductively-defined family μ_0,μ_1, …,μ_k of distributions, where μ_i is supported on functions [2^i]→[m^i].
The distribution μ_0 is supported on the only function that maps 0 to 0.
Assume that μ_i is already defined and let us define μ_i+1.
In order to do that, we independently sample f_0 and f_1 from μ_i and a from [m-1].  The corresponding function f in μ_i+1 is given by

    f(x) = 
    
    a· m^i + f_0(x),    if 0≤ x< 2^i;
    
    (a+1)m^i + f_1(x-2^i),    if 2^i≤ x< 2^i+1.


For an alternative way of defining μ, let us assume that the argument x is written in binary and the value f(x) in m-ary.
We prepend leading zeroes if necessary so that each number has exactly k digits.
We enumerate the digits from left to right with the elements of [k], so that the 0-th digit is the most significant one, and the (k-1)-st digit is the least significant one.
For each binary string s of length strictly less than k, sample an element a_s from [m-1] independently and uniformly at random.
The i-th digit of f(x) is defined as a_s+b, where s is the prefix of x of length i and b is the i-th bit of x.
It is easy to see that both definitions of μ are equivalent, and that any function f from the support of μ is monotone.

The distribution ν is defined as the uniform mixture of the following distributions ν^j for j∈[k].
The function g∼ν^j is defined as g(x) = f(x⊕ 2^k-1-j) when f is sampled from μ.  Here ⊕ denotes the bit-wise XOR function.
In other words, the jth bit of the argument is flipped before applying f.
Alternatively, we may say that g∼ν^j is defined as in the case of μ with the exception that the j-th digit of g(x) is a_s+(1-b) instead of a_s+b.



Any function g in the support of ν^j is 1/2-far from monotone.


Consider two input strings x<y that differ only in the j-th bit.
By the definition of ν^j we have g(x)>g(y), thus, {x,y} is a monotonicity-violating pair.  We have 2^k-1 such disjoint pairs, and every monotone function differs from g on at least one element of each pair.


Now we are ready to start with the proof of thm:main.  Assume towards contradiction that there exists a randomised 1/2-tester  with query complexity o(k).
Using standard error reduction, we may assume that  errs with probability at most 1/8 on each input.  Let λ be the uniform mixture of μ and ν.
Clearly,  errs with probability at most 1/8 on λ.
The randomised algorithm  can be defined as a probability distribution on deterministic query algorithms of the same query complexity, hence, one of the deterministic algorithms in the support of  errs with probability at most 1/8 on λ.
Thus, we may assume  is a deterministic query algorithm.
The error probability 1/8 on λ implies that on μ and ν we have

    _f∼μ [ accepts f] ≥3/4    and    _g∼ν [ accepts g] ≤1/4.

Also, we may assume that k is large enough, so that the query complexity of the deterministic query algorithm  is less than k/2.

So,  is a decision tree.  Its leaves are specified by assignments in the sense that  terminates its work on input f in a leaf given by assignment α if and only if f agrees with α.  Moreover, the weight of each such α does not exceed the query complexity of .
We partition all these assignments α into two parts as follows.
We say that an integer ℓ∈ [r] is good if it contains no digit 0 and no digit m-1 (in the m-ary representation as before).  Otherwise, ℓ is bad.
We say that an assignment α is good if all the elements in its image are good.  Otherwise, α is bad.
Finally, a leaf of  is good iff the corresponding assignment is good.



The probability that  ends its work in a bad leaf when run on an input f sampled from μ is o(1).


For each x in the domain of f, the value f(x) is bad only if one of the k elements a_s_0,a_s_1,…,a_s_k-1 has value 0 or m-2, where s_i is the prefix of x of length i.
Thus, the probability of  to terminate in a bad leaf is at most the probability of finding an element a_s with value in {0,m-2} with k/2 queries, where on each query it is allowed to test the values of k different a_s's.
Since the a_s's are independent, and the probability of a_s∈{0,m-2} is 2/(m-1), we get, using the standard bound on search, that the probability of succeeding is at most
k/2· k·2/m-1 = o(1).


fa_f∼μ [f⇁α]
ga_g∼ν [g⇁α]



For each good assignment α of weight at most k/2,

    ≤ 2· .



Before we start with the proof of this claim, let us show how thm:main follows from Claims <ref> and <ref>.
In the following, let C be the set of assignments which correspond to the accepting leaves of , let B⊆ C be the subset of bad assignments, and G⊆ C be the subset of good assignments.
Then,

    _f∼μ [ accepts f] 
    = ∑_α∈ B + ∑_α∈ G   
    ≤ o(1) + 2∑_α∈ G   ≤ o(1) + 2_g∼ν [ accepts g],

which is in contradiction with eqn:accprob if k is large enough.


It remains to prove clm:good.
Consider a good assignment α of weight at most k/2.  Let S be the domain of α.
We say that a pair x<y from S cuts an index j∈[k] iff their first j bits agree, and they disagree in the j-th bit.  In other words, there exists a∈ such that 

    2a ·2^k-j-1≤ x< (2a+1)·2^k-j-1≤ y <(2a+2)·2^k-j-1.

The assignment α cuts all the indices cut by the pairs in S.
clm:good follows from the following two lemmata.



If a good assignment α does not cut an index j, then

    _f∼μ [f⇁α]
    =
    _g∼ν^j [g⇁α].



By induction on i in the definition eqn:f of μ_i.
Let for brevity j' = k-j-1.
If j'<i, we define ν^j_i as the distribution over the functions g(x) = f(x⊕ 2^j') when f is sampled from μ_i.  If j'≥ i, we define ν^j_i = μ_i.
We prove that 

    _f∼μ_i [f⇁α]
    =
    _g∼ν^j_i [g⇁α]

for every good assignment α from [2^i] to [m^i] that does not cut the index j.

The base case i=0 is trivial.  (Actually, the statement is trivial for all i≤ j'.)
Assume eqn:agree is proven for i, and let us prove it for i+1.
Let S be the domain of α.  There are two cases.

First, assume both S∩[2^i] and S∩ [2^i..2^i+1] are non-empty.
This means that α cuts k-i-1, hence, i j'.
Also, we may assume there exists 1≤ a≤ m-3 such that  α([2^i])⊆ [am^i.. (a+1)m^i] and α([2^i..2^i+1])⊆ [(a+1)m^i..(a+2)m^i], since otherwise both sides of eqn:agree are 0.
Under these assumptions,

    _f∼μ_i+1 [f⇁α]
    =
    1/m-1_f_0∼μ_i [f_0⇁α_0]
    _f_1∼μ_i [f_1⇁α_1],

where f_0 and f_1 are obtained reversely from eqn:f, and α_0 and α_1 are defined similarly:
α_0(i) = α(i) m^i and α_1(i) = α(i+2^i) m^i for all i∈ [2^i].
Both assignments are good, and they do not cut the index j.

Similarly, since i j':

    _g∼ν^j_i+1 [g⇁α]
    =
    1/m-1_g_0∼ν^j_i [g_0⇁α_0]
    _g_1∼ν^j_i [g_1⇁α_1].

By the inductive assumption, we have the required equality.

Now assume one of S∩[2^i] and S∩ [2^i..2^i+1] is empty.
We consider the case S⊆[2^i], the second one being similar.
Again, we can assume there exists 1≤ a≤ m-2 such that  α([2^i])⊆ [am^i.. (a+1)m^i].  Then,

    _f∼μ_i+1 [f⇁α]
    =
    1/m-1_f_0∼μ_i [f_0⇁α_0]

and, no matter whether i=j' or not,

    _g∼ν^j_i+1 [g⇁α]
    =
    1/m-1_g_0∼ν^j_i [g_0⇁α_0],

and again we have the required equality by the inductive assumption.




An assignment α of weight t cuts at most t-1 indices in [k].


Let S be the domain of α, and let J⊆[k] be the set of indices that α cuts.

Let us construct a graph G as follows.  Its vertex set is S.  For every index j∈ J take one arbitrary pair of elements x,y∈ S that cuts j and connect x and y by an edge.  We say that the edge xy cuts j.

We claim that the graph G is acyclic, from which the statement of the lemma follows.
Assume that G contains a simple cycle.  Consider an edge xy that cuts the minimal index j on this cycle.  Then x and y disagree in the j-th bit.  On the other hand, considering the remaining part of the cycle, we see that x and y agree in the j-th bit.  A contradiction, hence, G is acyclic.


By lem:cut, there are at least k/2 indices not cut by α, and using lem:goodalpha, we have

    2·≥2/k∑_j:α does not cut j_g∼ν^j [g⇁α] ≥2/k·k/2· = ,

proving clm:good.




§ THE CASE OF SMALL 



In this section, we briefly describe how the result of thm:main can be extended to arbitrary values of , and give an improved version of the algorithm by Ergün  <cit.>.



If ≤ 1/2, the complexity of -testing a function f[n]→ [r] for monotonicity is 

    Ω[minlog( n)/, log ( r)/loglog ( r)].



tmuμ
tnuν

The proof closely follows that of thm:main.  We will briefly describe the construction and the proof using the notation of sec:main.

Let ℓ be a positive integer and assume =1/(2ℓ).  We will construct probability distributions  and  on functions f [ℓ 2^k]→ [ℓ k^3k] such that all functions in the support of  are monotone,  functions in the support of  are -far from monotone, and it takes Ω(ℓ k) queries to distinguish  and .
Expressing ℓ k in terms of  and n or in terms of  and r gives the required bound.

Let μ and ν be as in sec:main.  For s∈[ℓ], independently sample f_s from μ.  Define f∼ as

    f(s· 2^k+x) = s· k^3k + f_s(x)

for all s∈[ℓ] and x∈[2^k].
The distribution  is defined as the uniform mixture of ^t,j as t ranges over [ℓ] and j over [k].  The corresponding function f∼^t,j is defined as in eqn:tmu with exception that f_t is sampled from ν^j instead of μ.
It is easy to see that functions in the support of  are monotone, and, using clm:non-monotone, that functions in the support of  are -far from monotone.

Informally, it takes Ω(ℓ k) queries to distinguish  and  because we are searching for one non-monotone distribution ν^j among ℓ independent distributions.
Formally, we may proceed as follows.  Assume towards contradiction that there exists a deterministic query algorithm  that makes less than ℓ k/4 queries, accepts  with probability at least 3/4 and accepts  with probability at most 1/4.

Using the same reasoning as in clm:bad, the expected number of bad elements found by  when run on  is O(ℓ k^2/m) = o(ℓ).  We call an assignment α on [ℓ 2^k] bad if it has more than ℓ/4 bad elements in its image.  Otherwise, we call α good.  By Markov's inequality, the probability  terminates in a bad assignment when executed on  is o(1).

Now consider a good assignment α of weight at most ℓ k/4.
It corresponds to ℓ sub-assignments α_s on [2^k] defined by α_s(x) = α(s·2^k+x)  k^3k.
Using clm:good, we get that

    _f∼ [f⇁α] = _g∼^t,j [g⇁α]

if the sub-assignment α_t is good and does not cut j.  Using that there are at most ℓ/4 bad α_s and lem:cut, we have that there are at least ℓ k/2 pairs (t,j) satisfying eqn:notcutting.
Hence,

    _f∼ [f⇁α] ≤ 2 ·_g∼ [g⇁α].

Now we finish the proof as in sec:main.



Assume n≥ 2.  
Then, there exists a non-adaptive 1-sided algorithm that tests a function f[n]→ [r] for monotonicity using O[log( n)/] queries.


Combined with the result of thm:witheps, we get that complexity of this problem is Θ[log( n)/] if n≥ 2, and Θ(n) otherwise.

The algorithm is inspired by that of Ergün  <cit.>.

    .9
      *  Repeat Θ(1/) times:
        
      *  Choose x∈[n] uniformly at random.
            
      *  Query f(x).
            
      *  For i=0,…,[log ( n)]:
            
      *  Let w be the largest multiple of 2^i strictly smaller than x, and y be the smallest multiple of 2^i strictly larger than x.  (If any of them is outside [n], do not use it on the next steps.)
                
      *  Query f(w) and f(y).
                
      *  If f(w)>f(x) or f(x)>f(y), reject the function f.
            
      *  If no contradiction to monotonicity was found, accept.



Clearly, the query complexity of the algorithm is O[log( n)/], it is non-adaptive, and it always accepts a monotone function f.
Assume now that f is -far from monotone.


If f is -far from monotone, there exists a collection of pairwise disjoint pairs (x_1,y_1),…,(x_t, y_t) for t = [ n/2] such that, for all i,
x_i<y_i, f(x_i)>f(y_i), and y_i - x_i ≤ n.


The pairs can be constructed using the following algorithmic procedure.
Start with S [n] and i 1.  We treat S as a sorted list.
While i≤ t, choose two neighbouring elements x_i<y_i in S such that f(x_i)>f(y_i), remove x_i and y_i from S, and increment i.

It remains to prove that (a) such a pair (x_i,y_i) will always exist and (b) that y_i-x_i≤ n.
For (a), observe that i≤ t implies that we have removed strictly less than n elements from S so far.  
Since f is -far from monotone, we have that f restricted to S is not monotone (otherwise, it would be possible to extend f|_S to a monotone function on all [n]).
The existence of the pair (x_i,y_i) is now obvious.

For (b), again, observe that we have removed less than n-1 elements from S so far.  The elements x_i and y_i are neighbouring in S, which means they are at distance at most n in the original list [n].




Assume x and y satisfy x<y, f(x)>f(y) and y-x≤ n.
Then one element z∈{x,y} of these two is such that the algorithm will reject if it chooses z on step 1(a).


If y = x+1, the algorithm will reject if it chooses either of x or y.
So, assume y≥ x+2.

We claim that there exists an integer 0≤ i≤[log( n)] such that there is unique multiple of 2^i strictly between x and y.  
Indeed, there is at least one for i=0 and at most one for i = [log( n)].  Also, it is not possible that there is more than one for some value of i and zero for i+1.

Let w be this unique multiple of 2^i.  
If f(w) < f(x), then it will be detected if the algorithm chooses x on step 1(a).
If f(w) ≥ f(x), then f(w) > f(y), and it will be detected if the algorithm chooses y on step 1(a).


By the previous two lemmata, there exist [ n/2] values of x on which the algorithm rejects should it choose any of them on step 1(a).
The probability of choosing one of them on one iteration of the loop is Ω().  The probability to choose any of them on one of the Θ(1/) iterations of the loop is Ω(1).





§ THE CASE OF HYPERGRIDS


In this section, we show how our results can be transformed into a lower bound for testing monotonicity on the hypergrid.


If ≤ 1/2, the complexity of -testing a function f[n]^d→ [r] for monotonicity is 

    Ω[minlog( n^d)/, log ( r)/loglog ( r)].



In terms of n, the lower bound can be expressed as Ω(^-1dlog n - ^-1log^-1).

Consider the functions defined in the proof of thm:witheps.
Assume that ℓ = 2^a for some integer a, and choose k so that a+k = db for some integer b.
We consider the domain of the input functions [ℓ 2^k] = [2^a+k] as [2^b]^d, where we break the binary representation of x∈[2^a+k] into d groups of b bits.

If a function is monotone on [2^a+k], it is still monotone when considered on [2^b]^d.  
Also, the analysis of the algorithm does not involve the order relation defined on the domain of the input functions.  
The only thing that might go wrong is that the functions in the support of  are no longer -far from monotone when considered on [2^b]^d.  But this does not happen.  
Indeed, in the proof of clm:non-monotone, the monotonicity-violating pairs (x,y) differ in exactly one bit.  So if x<y in [2^a+k], this is still true in [2^b]^d, hence the proof of clm:non-monotone carries over.
Thus, all the functions in the support of  are -far from monotone.
The statement of the theorem now follows from the proof of thm:witheps.





§ ACKNOWLEDGEMENTS

I am grateful to Eric Blais for introducing me to this problem, and for his encouragement to work on it, as well as for pointing out Ref. <cit.>.
I would like to thank Dmitry Gavinsky, Ansis Rosmanis, and Ronald de Wolf for helpful discussions, and anonymous referees for their suggestions.
The construction of thm:witheps is due to Ronald de Wolf.

This research is supported by the ERDF project number 1.1.1.2/I/16/113.
Part of this work was done while visiting Institute of Mathematics of the Czech Academy of Sciences in Prague, and Centre for Quantum Technologies in Singapore.  I would like to thank Dmitry Gavinsky, Pavel Pudlák, and Miklos Santha for hospitality.

habbrvM


