# «Abstract. For positive integers n, d, consider the hypergrid [n]d with the coordinate-wise product partial ordering denoted by. A function f : [n]d ...»

An Optimal Lower Bound for Monotonicity

Testing over Hypergrids

Deeparnab Chakrabarty1 and C. Seshadhri2

1

Microsoft Research India

dechakr@microsoft.com

2

Sandia National Labs, Livermore

scomand@sandia.gov

Abstract. For positive integers n, d, consider the hypergrid [n]d with

the coordinate-wise product partial ordering denoted by. A function

f : [n]d → N is monotone if ∀x y, f (x) ≤ f (y). A function f is ε-

far from monotone if at least an ε-fraction of values must be changed to make f monotone. Given a parameter ε, a monotonicity tester must distinguish with high probability a monotone function from one that is ε-far.

We prove that any (adaptive, two-sided) monotonicity tester for func- tions f : [n]d → N must make Ω(ε−1 d log n − ε−1 log ε−1 ) queries. Recent upper bounds show the existence of O(ε−1 d log n) query monotonicity testers for hypergrids. This closes the question of monotonicity testing for hypergrids over arbitrary ranges. The previous best lower bound for general hypergrids was a non-adaptive bound of Ω(d log n).

Keywords: Monotonicity testing, sublinear algorithms, lower bounds 1 Introduction Given query access to a function f : D → R, the ﬁeld of property testing [1,2] deals with the problem of determining properties of f without reading all of it. Monotonicity testing [3] is a classic problem in property testing. Consider a function f : D → R, where D is some partial order given by “ ”, and R is a y (in D), f (x) ≤ f (y).

total order. The function f is monotone if for all x The distance to monotonicity of f is the minimum fraction of values that need to be modiﬁed to make f monotone. More precisely, deﬁne the distance between functions d(f, g) as |{x : f (x) = g(x)}|/|D|. Let M be the set of all monotone functions. Then the distance to monotonicity of f is ming∈M d(f, g).

A function is called ε-far from monotone if the distance to monotonicity is at least ε. A property tester for monotonicity is a, possibly randomized, algorithm that takes as input a distance parameter ε ∈ (0, 1), error parameter δ ∈ [0, 1], Sandia National Laboratories is a multi-program laboratory managed and operated by Sandia Corporation, a wholly owned subsidiary of Lockheed Martin Corporation, for the U.S. Department of Energy’s National Nuclear Security Administration under contract DE-AC04-94AL85000.

and query access to an arbitrary f. If f is monotone, then the tester must accept with probability 1 − δ. If it is ε-far from monotone, then the tester rejects with probability 1 − δ. (If neither, then the tester is allowed to do anything.) The aim is to design a property tester using as few queries as possible. A tester is called one-sided if it always accepts a monotone function. A tester is called nonadaptive if the queries made do not depend on the function values. The most general tester is an adaptive two-sided tester.

Monotonicity testing has a rich history and the hypergrid domain, [n]d, has received special attention. The boolean hypercube (n = 2) and the total order (d = 1) are special instances of hypergrids. Following a long line of work [4,3,5,6,7,8,9,10,11,12,13,14], previous work of the authors [15] shows the existence of O(ε−1 d log n)-query monotonicity testers. Our result is a matching adaptive lower bound that is optimal in all parameters (for unbounded range functions). This closes the question of monotonicity testing for unbounded ranges on hypergrids. This is also the ﬁrst adaptive bound for monotonicity testing on general hypergrids.

**Theorem 1. Any (adaptive, two-sided) monotonicity tester for functions f :**

[n]d → N requires Ω(ε−1 d log n − ε−1 log ε−1 ) queries.

1.1 Previous work The problem of monotonicity testing was introduced by Goldreich et al. [3], with an O(n/ε) tester for functions f : {0, 1}n → {0, 1}. The ﬁrst tester for general hypergrids was given by Dodis et al. [5]. The upper bound of O(ε−1 d log n) for monotonicity testing was recently proven in [15]. We refer the interested reader to the introduction of [15] for a more detailed history of previous upper bounds.

There have been numerous lower bounds for monotonicity testing. We begin by summarizing the state of the art. The known adaptive lower bounds are Ω(log n) for the total order [n] by Fischer [9], and Ω(d/ε) for the boolean hypercube {0, 1}d by Brody [16]. For general hypergrids, Blais, Raskhodnikova, and Yaroslavtsev [17] recently proved the ﬁrst result, a non-adaptive lower bound of Ω(d log n). Theorem 1 is the ﬁrst adaptive bound for monotonicity testing on hypergrids and is optimal (for arbitrary ranges) in all parameters.

Now for the chronological documentation. The ﬁrst lower bound was the non-adaptive bound of Ω(log n) for the total order [n] by Ergun et al. [4]. This was extended by Fischer [9] to an (optimal) adaptive bound. For the hypercube domain {0, 1}d, Fischer et al. [7] proved the ﬁrst non-adaptive lower bound of √ Ω( d). (This was proven even for the range {0, 1}.) This was improved to Ω(d/ε) by Br¨ et al. [18]. Blais, Brody, and Matulef [14] gave an ingenious reduction ıet from communication complexity to prove an adaptive, two-sided bound of Ω(d).

(Honing this reduction, Brody [16] improved this bound to Ω(d/ε).) The nonadaptive lower bounds of Blais, Raskhodnikova, and Yaroslavtsev [17] were also achieved through communication complexity reductions.

We note that our theorem only holds when the range is N, while some previous results hold for restricted ranges. The results of [14,16] provide lower bounds for √ range [ d]. The non-adaptive bound of [17] holds even when the range is [nd].

In that sense, the communication complexity reductions provide stronger lower bounds than our result.

**1.2 Main ideas**

The starting point of this work is the result of Fischer [9], an adaptive lower bound for monotonicity testing for functions f : [n] → N. He shows that adaptive testers can be converted to comparison-based testers, using Ramsey theory arguments. A comparison-based tester for [n] can be easily converted to a non-adaptive tester, for which an Ω(log n) bound was previously known. We make a fairly simple observation. The main part of Fischer’s proof actually goes through for functions over any partial order, so it suﬃces to prove lower bounds for comparison-based testers. (The reduction to non-adaptive testers only holds for [n].) We then prove a comparison-based lower bound of Ω(ε−1 d log n−ε−1 log ε−1 ) for the domain [n]d. As usual, Yao’s minimax lemma allows us to focus on determinstic lower bounds over some distribution of functions. The major challenge in proving (even non-adaptive) lower bounds for monotonicity is that the tester might make decisions based on the actual values that it sees. Great care is required to construct a distribution over functions whose monotonicity status cannot be decided by simply looking at the values. But a comparison-based tester has no such power, and optimal lower bounds over all parameters can be obtained with a fairly clean distribution.

2 The reduction to comparison based testers Consider the family of functions f : D → R, where D is some partial order, and R ⊆ N. We will assume that f always takes distinct values, so ∀x, y, f (x) = f (y).

Since we are proving lower bounds, this is no loss of generality.

Deﬁnition 1. An algorithm A is a (t, ε, δ)-monotonicity tester if A has the following properties. For any f : D → R, the algorithm A makes t (possibly randomized) queries to f and then outputs either “accept” or “reject”. If f is monotone, then A accepts with probability 1 − δ. If f is ε-far from monotone, then A rejects with probability 1 − δ.

Eq. (1) ensures the decisions of the tester at step (s + 1) must form a probability distribution. Eq. (2) implies that the tester makes at most t queries.

For any positive integer s, let R(s) denote the set of unordered subets of R of cardinality s. For reasons that will soon become clear, we introduce new functions as follows. For each s, x ∈ Ds, y ∈ D, and each permutation σ : [s] → [s], we associate functions qx,σ : R(s) → [0, 1], with the semantic y

function on R(s). In other words, the (s + 1)th decision of the tester given that the ﬁrst s questions is x, depends only on the ordering of the answers received, and not on the values of the answers.

The following theorem is implicit in the work of Fischer [9].

** Theorem 2. Suppose there exists a (t, ε, δ)-monotonicity tester for functions f : D → N.**

Then there exists a comparison-based (t, ε, 2δ)-monotonicity tester for functions f : D → N.

This implies that a comparison-based lower bound suﬃces for proving a general lower bound on monotonicity testing. We provide a proof of the above theorem in the next section for completeness.

Furthermore, prej (a) ≥ prej (a).

ˆx x The p-functions describe a new discrete tester A that makes at most t ˆ queries. We argue that A is a (t, ε, 2δ)-tester. Given a function f that is either monotone or ε-far from monotone, consider a sequence of queries x1,..., xs after which A returns a correct decision ℵ. Call such a sequence good, and let α denote the probability this occurs. We know that the sum of probabilities over all good query sequences is at least (1 − δ). Now, α := px1 · px2 (f (x1 )) · px31,x2 ) (f (x1 ), f (x2 )) · · · · pℵ 1,...,xs ) (f (x1 ),..., f (xs )) x1 (x (x Two cases arise. Suppose all of the probabilities in the RHS are ≥ 10t/δK.

Then, the probability of this good sequence arising in A is at least (1−δ/10t)t α ≥ α(1 − δ/2). Otherwise, suppose some probability in the RHS is 10t/δK. Then the total probability mass on such good sequences in A is at most 10t/δK · |D|t ≤ δ/2. Therefore, the probability of good sequences in A is at least (1 − 3δ/2)(1 − δ/2) ≥ 1 − 2δ. That is, A is a (t, ε, 2δ) tester.

We introduce some Ramsey theory terminology. For any positive integer i, a ﬁnite coloring of N(i) is a function coli : N(i) → {1,..., C} for some ﬁnite number C. An inﬁnite set X ⊆ N is called monochromatic w.r.t coli if for all sets A, B ∈ X (i), coli (A) = coli (B). A k-wise ﬁnite coloring of N is a collection of k colorings col1,..., colk. (Note that each coloring is over diﬀerent sized tuples.) An inﬁnite set X ⊆ N is k-wise monochromatic if X is monochromatic w.r.t. all the coli s.

The following is a simple variant of Ramsey’s original theorem. (We closely follow the proof of Ramsey’s theorem as given in Chap VI, Theorem 4 of [19].) Theorem 3. For any k-wise ﬁnite coloring of N, there is an inﬁnite k-wise monochromatic set X ⊆ N.

Proof. We proceed by induction on k. If k = 1, then this is trivially true; let X be the maximum color class. Since the coloring is ﬁnite, X is inﬁnite. We will now iteratively construct an inﬁnite set of N via induction.

Start with a0 being the minimum element in N. Consider a (k − 1)-wise coloring of (N \ {a0 }) col1,..., colk−1, where coli (S) := coli+1 (S ∪ a0 ). By the induction hypothesis, there exists an inﬁnite (k − 1)-wise monochromatic set A0 ⊆ N \ {a0 } with respect to coloring coli s. That is, for 1 ≤ i ≤ k, and any set 0 S, T ⊆ A0 with |S| = |T | = i − 1, we have coli (a0 ∪ S) = coli (a0 ∪ T ) = Ci, 0 0 0 say. Denote the collection of these colors as a vector C0 = (C1, C2,..., Ck ).

Subsequently, let a1 be the minimum element in A0, and consider the (k −1)wise coloring col of (A0 \ {a1 }) where coli (S) = coli+1 (S ∪ {a1 }) for S ⊆ A0 \ {a1 }. Again, the induction hypothesis yields an inﬁnite (k − 1)-wise monochromatic set A1 as before, and similarly the vector C1. Continuing this procedure, we get an inﬁnite sequence a0, a1, a2,... of natural numbers, an inﬁnite sequence of vectors of k colors C0, C1,..., and an inﬁnite nested sequence of inﬁnite sets A0 ⊃ A1 ⊃ A2.... Every Ar contains as, ∀s r and by construction, any set i ({ar } ∪ S), S ⊆ Ar, |S| = i − 1, has color Cr. Since there are only ﬁnitely many colors, some vector of colors occurs inﬁnitely often as Cr1, Cr2,.... The corresponding inﬁnite sequence of elements ar1, ar2,... is k-wise monochromatic.

**Proof. (of Theorem 2) Suppose there exists a (t, ε, δ)-tester for functions f :**

D → N. We need to show there is a comparison-based (t, ε, 2δ)-tester for such functions.

By Lemma 1, there is a discrete (t, ε, 2δ)-tester A. Equivalently, we have the y functions qx,σ as described in the previous section. We now describe a t-wise ﬁnite coloring of N. Consider s ∈ [t]. Given a set A ⊆ N(s), cols (A) is a vector indexed by (y, x, σ), where y ∈ D, x ∈ Ds, and σ is a s-permutation, whose y entry is qx,σ (A). The domain is ﬁnite, so the number of dimensions is ﬁnite. Since the tester is discrete, the number of possible colors entries is ﬁnite. Applying Theorem 3, we know the existence of a t-wise monochromatic inﬁnite set R ⊆ N.

We have the property that for any y, x, σ, and any two sets A, B ∈ R(s), we have y y qx,σ (A) = qx,σ (B). That is, the algorithm A is a comparison based tester for functions with range R.

Consider the strictly monotone map φ : N → R, where φ(b) is the bth element of R in sorted order. Now given any function f : D → N, consider the function φ ◦ f : D → R. Consider an algorithm A which on input f runs A on φ ◦ f.

More precisely, whenever A queries a point x, it gets answer φ ◦ f (x). Observe that if f is monotone (or ε-far from monotone), then so is φ ◦ f, and therefore, the algorithm A is a (t, ε, 2δ)-tester of φ ◦ f. Since the range of φ ◦ f is R, A is comparison-based.

**3 Lower bounds**

We assume that n is a power of 2, set := log2 n, and think of [n] as {0, 1,..., n− 1}. For any number 0 ≤ z n, we think of the binary representation of z as an

-bit vector (z1, z2,..., z ), where z1 is the least signiﬁcant bit.

Consider the following canonical, one-to-one mapping φ : [n]d → {0, 1}d.