Adaptive Boolean Monotonicity Testing in Total Influence Time

arXiv:1801.02816v1 [cs.DS] 9 Jan 2018

Deeparnab Chakrabarty
Dartmouth College
deeparnab@dartmouth.edu

C. Seshadhri
University of California, Santa Cruz
sesh@ucsc.edu

Abstract
The problem of testing monotonicity of a Boolean function f : {0, 1}n → {0, 1} has received much attention
recently. Denoting the proximity parameter by ε, the best tester is the
e √n/ε2 ) tester of Khot-Minzer-Safra (FOCS 2015). Let I(f ) denote the total
non-adaptive O(
influence of f . We give an adaptive tester whose running time is I(f )poly(ε−1 log n).

1

Introduction

Consider the boolean hypercube {0, 1}n , endowed with the coordinate-wise partial order denoted
by ≺. A function f : {0, 1}n → {0, 1} is monotone if ∀x ≺ y, f (x) ≤ f (y). Let d(f, g), the distance
between two functions f, g, be |{x : f (x) 6= g(x)}|/2n . The distance to monotonicity, εf , is the
minimum distance of f to a monotone g. The problem of monotonicity testing is as follows. Given
query access to f and a proximity parameter ε > 0, design a (randomized) procedure that accepts if
f is monotone (εf = 0), and rejects if f is ε-far from monotone (εf > ε). Both the above guarantees
hold with probability at least 2/3. Such a procedure is called a monotonicity tester. A tester is
non-adaptive if the queries made are independent of the values of f , and adaptive otherwise. A
tester is one-sided if it accepts monotone functions with probability 1, and two-sided otherwise.
The problem of monotonicity testing over the hypercube has been the subject of much study [Ras99,
GGL+ 00, DGL+ 99, CS14, CST14, CDST15, KMS15, BB16, CWX17]. The first result was the
O(n/ε) tester by Goldreich et al. and Dodis et al. [GGL+ 00, DGL+ 99] (refer to Raskhodnikova’s
thesis [Ras99]). The authors unearthed a connection to directed isoperimetric theorems to give a
o(n) tester [CS14], whose analysis was further improved by Chen et al. [CST14]. In a remarkable
e √n/ε2 )-query non-adaptive, one-sided
result, Khot-Minzer-Safra (henceforth KMS) designed an O(
tester [KMS15]. The key ingredient is a directed analog of Talagrand’s isoperimetry theorem [Tal93].
√
The significance of the n bound of KMS to f is underscored by a nearly matching lower bound
by Fischer et al. for non-adaptive, one-sided testers [FLN+ 02]. A nearly matching two-sided, nonadaptive lower bound of Ω(n1/2−δ ) for any δ > 0 was showed by Chen et al. [CST14, CDST15]
using highly non-trivial techniques of generalized Central Limit Theorems.
In a major advance, Belovs and Blais [BB16] proved the first polynomial adaptive (two-sided)
e 1/3 ). Both of
e 1/4 ). This was further improved by Chen et al. [CWX17] to Ω(n
lower bound of Ω(n
these are highly non-trivial results, showing that challenges in arguing about adaptive monotonicity
3
testers. Interestingly, Belovs and Blais [BB16] show O(log n) + 2O(1/ε ) time adaptive monotonicity
testers for Regular Linear Threshold Functions, which form the hard distribution of the nearly
√
Ω( n) lower bound of Chen et al. [CST14, CDST15].

1

This leads to the main open problem in monotonicity testing of Boolean functions: Does adaptivity
always help?

1.1

Results

Given our (current) inability to resolve that question, we ask a refined, simpler question. Is there
√
some natural condition of functions under which the n non-adaptive complexity of KMS can be
beaten?
Let I(f ) denote the total influence (also called the average sensitivity) of f . Letting D be the
uniform distribution over all pairs (x, y) at Hamming distance 1, I(f ) := n · Pr(x,y)∼D [f (x) 6= f (y)].
Our main theorem follows.
Theorem 1.1. Consider the class of functions with total influence at most I. There exists a
one-sided, adaptive monotonicity tester for this class with running time O(I · poly(log n)/ε4 ).
√
Thus, for low influence functions, the KMS n bound can be (adaptively) beaten. The nonadaptive lower bound of Fischer et al. [FLN+ 02] only requires constant influence functions, so
√
Theorem 1.1 shows that adaptivity provably helps for such functions. For I(f ) ≫ n, a claim
of KMS (explained later) implies the existence of non-adaptive O(n/I(f ))) testers. The tradeoff
√
between Theorem 1.1 and this bound is basically n, the maximum possible influence of a monotone function. We note that all adaptive lower bound constructions have functions with influence
√
Θ( n) [BB16, CWX17].

2

Preliminaries

We use Hn to denote the standard (undirected) hypercube graph on {0, 1}n , where all pairs at
Hamming distance 1 are connected. An edge (x, y) of Hn is influential, if f (x) 6= f (y). The number
of influential edges is precisely I(f ) · 2n−1 . An influential edge (x, y) is a violating edge if x ≺ y,
f (x) = 1, and f (y) = 0. Our tester will perform random walks of Hn . Note that Hn is regular, so
this is a symmetric Markov Chain.
We crucially use the central result of KMS, in essence a directed analogue of Talagrand’s isoperimetric theorem.
Lemma 2.1. (Lemma 7.1 in [KMS15], paraphrased) Given any Boolean function f : {0, 1}n →
{0, 1} which is ε-far from being monotone, there exists a subgraph G = (A, B, E) of the hypercube
and parameters σ ∈ (0, 1), d ∈ Z>0 such that
•
•
•
•

Each edge (a, b) ∈ E with a ∈ A and b ∈ B is a violating edge.
|B| = σ · 2n .
The degree of each vertex in B is exactly d and the degree of each vertex in A is at most 2d.
σ 2 d = Θ(ε2 / log4 n).

We also mention a simpler lemma from KMS which we use.
√
Lemma 2.2. (Theorem 9.1 in [KMS15], paraphrased) If I(f ) > 6 n, then a constant fraction of
influential edges are violating edges.
√
When I(f ) > 6 n, one can find a violation in time O(n/I(f )) = O(I(f )) by simply sampling
√
random edges. Thus, we will focus on the case I(f ) ≤ 6 n.
2

Idea. Our analysis is short and follows the analysis of the KMS tester. The tester of KMS can be
throught of as performing random walks on the directed hypercube with orientation corresponding
to the partial order. Their analysis lower bounds the probability of encountering a violation. Our
insight is that one can perform an analogous analysis for walks on the undirected hypercube Hn .
Suppose we perform an ℓ-step random walk (on Hn ) from x that ends at y. If f (x) 6= f (y), then
the walk clearly passed through an influential edge. The power of adaptivity is that we can find
such an influential edge through binary search. This idea of using binary search is also present in
the algorithm of Belovs and Blais [BB16] to adaptively test regular linear threshold functions. We
bound the probability that this influential edge is a violation. Our insight is that, by setting the
length ℓ appropriately, this probability can be lower bounded by (essentially) 1/I(f ).

3

Tester

Let f : {0, 1}n → {0, 1} be a Boolean function over the hypercube with total influence I(f ).
Input: A Boolean function f : {0, 1}n → {0, 1} and a parameter ε ∈ (0, 1)
1.
2.
3.
4.

Choose k ∈R {0, 1, 2, . . . , ⌈log n⌉} uniformly at random. Set ℓ := 2k .
Choose x ∈ {0, 1}n uniformly at random.
Perform an ℓ-length random walk p on Hn starting from x to reach y ∈ {0, 1}n .
If f (x) 6= f (y):
(a) Perform binary search on p to find an influential edge (u, v) ∈ p.

(b) REJECT if (u, v) is a monotonicity violation.
5. If not REJECTED so far, then ACCEPT.

Figure 1: Adaptive Monotonicity Tester for Boolean Functions
Theorem 1.1 follows directly from the following.
√
Theorem 3.1. Assume
I(f) ≤ 6 n. If f is ε-far from being monotone, then Algorithm 1 rejects

4
with probability Ω I(f )εlog9 n .
Definition 3.2. Given a positive integer ℓ, we call a vertex x ∈ {0, 1}n ℓ-sticky if an ℓ-length
random walk from x on Hn contains no influential edges with probability ≥ 1/2. A vertex is called
non-ℓ-sticky otherwise. An edge is ℓ-sticky if both endpoints are ℓ-sticky.
The following simple monotonicity property follows from the definition.
Observation 3.3. If x is ℓ-sticky and ℓ′ < ℓ, then x is ℓ′ -sticky as well.
Lemma 3.4. The fraction of non-ℓ-sticky vertices of a hypercube is at most

2ℓ·I(f )
n .

Proof. Given x ∈ {0, 1}n and a positive integer ℓ > 0, define the random variable Zx,ℓ that is
the number of influential edges in a random walk of length ℓ starting from x. Therefore, x is
ℓ-non-sticky iff Pr[Zx,ℓ > 0] > 1/2. Let N denote the set of ℓ-non-sticky vertices.
3

Since Zx,ℓ is non-negative and integer valued we get Pr[Zx,ℓ > 0] ≤ E[Zx,ℓ ].
|N |/2n <

2
2 X
Pr[Zx,ℓ > 0] < n
n
2
2
x∈N

X

x∈{0,1}n

Pr[Zx,ℓ > 0] ≤

2
2n

X

E[Zx,ℓ ]

(1)

x∈{0,1}n

The RHS above is precisely twice the expected number of influential edges encountered in an ℓlength random walk starting from the uniform distribution on Hn . Let Pℓ denote the uniform
distribution on ℓ-length paths in Hn . For p ∼ Pℓ , pt denotes the tth edge in p,Pand let χ(e)
bePthe indicator for edge e being influential. The RHS of (1) is equal to 2Ep∼Pℓ [ t≤ℓ χ(pt )] =
2 t≤ℓ Ep∼Pℓ [χ(pt )]. Since the uniform distribution is stationary for random walks on Hn , the
distribution induced on pt is the uniform distribution on edges in Hn . Thus, Ep∼Pℓ [χ(pt )] = I(f )/n
and the RHS of (1) is 2ℓ · I(f )/n.
For any integer ℓ > 0, let Fℓ be the set of ℓ-sticky violating edges. That is,
Fℓ := {(x, y) ∈ Hn : (x, y) is violating and, x, y are ℓ-sticky}
Lemma 3.5.If ℓ is the
 length of the random walk chosen in Step 1, then Algorithm 1 rejects with
ℓ |Fℓ |
probability Ω n · 2n .
Proof. Fix an edge (u, v) ∈ Fℓ . Let p = (e1 , . . . , eℓ ) be the edges of a random walk p. Each
edge et for 1 ≤ t ≤ ℓ is a uniform random edge of Hn . Therefore, for any fixed edge (u, v),
Pr[et = (u, v)] = n22n .
t to be the event that the tth edge of p is (u, v) and no other edge
Now, given 1 ≤ t ≤ ℓ, define Eu,v
t . Furthermore,
of p is influential. Since (u, v) is itself influential, Eu,v is the disjoint union ∨ℓt=1 Eu,v
′
′
for two distinct edges (u, v) and (u , v ) in Fℓ , the events Eu,v and Eu′ ,v′ are disjoint.
Observe that
_
X
Eu,v ] =
Pr[Eu,v ]
(2)
Pr[Algorithm 1 rejects given ℓ] ≥ Pr[
(u,v)∈Fℓ

(u,v)∈Fℓ

The equality follows since the events are mutually exclusive. The inequality follows since if Eu,v
occurs then the end points of p must have differing values and binary search on p will return the
violation (u, v).
t . For this event to occur, e must be (u, v). Consider the conditional
Consider the event Eu,v
t
t
| et = (u, v)]. Let Fu be the event that a (t − 1)-length random walk from u
probability Pr[Eu,v
contains no influential edges, and let Fv be the event that an independent (ℓ − t)-length random
walk from v contains no influential edges.
t
Claim 3.6. Pr[Eu,v
| et = (u, v)] = Pr[Fu ∧ Fv ] = Pr[Fu ] · Pr[Fv ]

Proof. Conditioned on et = (u, v), the distribution of the first (t − 1) steps of the random walk is
the uniform distribution of (t − 1)-length paths that end at u. This is the same distribution of the
(t − 1)-length random walk starting from u. The distribution of the last (ℓ − t) steps, conditioned
on et = (u, v), is the (ℓ − t)-length random walk starting from v.

4

Since (u, v) is an ℓ-sticky edge, by Obs 3.3 and Definition 3.2, Pr[Fu ] ≥ 1/2 and Pr[Fv ] ≥ 1/2. The
proof is completed by plugging the following bound into (2).
Pr[Eu,v ] =

ℓ
X
t=1

t
Pr[Eu,v
]=

ℓ
X
t=1

t
Pr[et = (u, v)] · Pr[Eu,v
| et = (u, v)] =

≥

ℓ
2 X
t
Pr[Eu,v
| et = (u, v)]
n2n t=1

ℓ
4n2n

We complete the proof of Theorem 3.1.
Proof of Theorem 3.1. Let G = (A, B, E), σ, d be as in Lemma 2.1.
√
First, we take care of a corner case. Suppose σ < 100/ n. Since σ 2 d = Ω(ε2 / log4 n), we
√
get σd = Ω(ε2 n/ log4 n). Since the number of violating edges is ≥ |E| = σd2n and since each
√
violating edge is influential, we get that I(f ) ≥ |E|/2n = Ω(ε2 n/ log4 n). With probability
1/ log n, Algorithm 1 sets ℓ = 1, in which case the tester basically checks whether a uniform
random edge in Hn is a violation. Conditioned on setting ℓ = 1, the rejection probability is
√
√
Ω(2|E|/n2n ) = Ω(ε2 / n log4 n) = Ω(ε4f /I(f ) log8 n). Thus, in the case σ < 100/ n, we have
proved Theorem 3.1.
√
√
nσ
Henceforth, assume that σ ≥ 100/ n. Since I(f ) ≤ 6 n, we deduce that 16·I(f
) > 1. Thus, there
∗

)
σ
exists a non-negative power of 2 (call it ℓ∗ ) such that 16
< ℓ ·I(f
≤ σ8 .
n
′
′
∗
Let A and B be the subset of A and B that are ℓ -sticky. Let E ′ ⊆ E be the edges with end
points in A′ and B ′ . Note that any edge of E ′ ⊆ Fℓ∗ . By Lemma 3.4, we get that the fraction of
ℓ∗ -non-sticky nodes is at most 2ℓ∗ · I(f )/n ≤ σ/4. Since the degree of any node in G in Lemma 2.1
is ≤ 2d, we get
σd2n
σ · 2n
=
.
|Fℓ∗ | ≥ |E ′ | ≥ |E| − (2d) ·
4
2
The probability the algorithm chooses ℓ = ℓ∗ is 1/log n. Lemma 3.5 gives us

Pr[Algorithm rejects] ≥
≥
≥
≥
≥

1
· Pr[Algorithm rejects|ℓ = ℓ∗ ]
log n
 ∗

ℓ |Fℓ∗ |
1
·
· n
(by Lemma 3.5)
log n
n
2
ℓ∗ σd
1
·
·
log n n 2


1
σ2 d
·
(plugging ℓ∗ ≥ σn/(16 · I(f )))
I(f )
32 log n
1
ε2
(by Lemma 2.1)
·
I(f ) log5 n

5

References
[BB16]

Aleksandrs Belovs and Eric Blais. A polynomial lower bound for testing monotonicity.
In Proceedings of the Symposium on Theory of Computing (STOC), pages 1021–1032,
2016. 1, 2, 3

[CDST15] Xi Chen, Anindya De, Rocco A. Servedio, and Li-Yang Tan. Boolean function monotonicity testing requires (almost) O(n1/2 ) non-adaptive queries. In Proceedings of the
Symposium on Theory of Computing (STOC), pages 519–528, 2015. 1
[CS14]

Deeparnab Chakrabarty and C. Seshadhri. An o(n) monotonicity tester for boolean
functions over the hypercube. SIAM Journal on Computing, 2014. 1

[CST14]

Xi Chen, Rocco A. Servedio, and Li-Yang. Tan. New algorithms and lower bounds
for monotonicity testing. In Proceedings of Foundations of Computer Science (FOCS),
pages 286–295, 2014. 1

[CWX17] Xi Chen, Erik Waingarten, and Jinyu Xie. Beyond talagrand: New lower bounds for
testing monotonicity and unateness. In ACM Symposium on Theory of Computation
(STOC), 2017. 1, 2
[DGL+ 99] Yevgeny Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, and
Alex Samorodnitsky. Improved testing algorithms for monotonicity. Proceedings of
the 3rd International Workshop on Randomization and Approximation Techniques in
Computer Science (RANDOM), pages 97–108, 1999. 1
[FLN+ 02] Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, and Ronitt Rubinfeld.
Monotonicity testing over general poset domains. Proceedings of the 34th Annual ACM
Symposium on the Theory of Computing (STOC), pages 474–483, 2002. 1, 2
[GGL+ 00] Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, and Alex Samordinsky.
Testing monotonicity. Combinatorica, 20:301–337, 2000. 1
[KMS15]

Subhash Khot, Dor Minzer, and Muli Safra. On monotonicity testing and boolean
isoperimetric type theorems. In IEEE Annual Symposium on Foundations of Computer
Science, FOCS, 2015. 1, 2

[Ras99]

Sofya Raskhodnikova. Monotonicity testing. Masters Thesis, MIT, 1999. 1

[Tal93]

Michel Talagrand. Isoperimetry, logarithmic sobolev inequalities on the discrete cube,
and margulis graph connectivity theorem. Geom. Func. Anal., 3(3):295–314, 1993. 1

6

