Testing Unateness of Real-Valued Functions∗
Roksana Baleshzar†

Meiram Murzabulatov†

Ramesh Krishnan S. Pallavoor†

arXiv:1608.07652v1 [cs.DS] 27 Aug 2016

Sofya Raskhodnikova†

Abstract
We give a unateness tester for functions of the form f : [n]d → R, where n, d ∈ N and
R ⊆ R with query complexity O( d log(max(d,n))
). Previously known unateness testers work only

for Boolean functions over the domain {0, 1}d . We show that every unateness tester for realvalued functions over hypergrid has query complexity Ω(min{d, |R|2 }). Consequently, our tester
is nearly optimal for real-valued functions over {0, 1}d . We √
also prove that every nonadaptive,
1-sided error unateness tester for Boolean functions needs Ω( d/) queries. Previously, no lower
bounds for testing unateness were known.

1

Introduction

We study property testing unateness of functions of the form f : [n]d → R, where n, d ∈ N and
R ⊆ R. Unate functions are used in mathematics and other technical disciplines, for example in
tautology checking [14, 15] and in switching theory [17]. For x, y ∈ [n]d , where x = x1 , . . . , xd and
n
P
y = y1 , . . . , yd , we define |x − y|1 =
|xi − yi |. Two points x, y are neighbours if |x − y|1 = 1. A
i=1

function f : [n]d → R is unate if each dimension i ∈ [d] can be assigned an associated direction up or
down; the direction is up if f (x) ≤ f (y) for all neighbours x, y where yi = xi + 1; and the direction
is down if f (x) ≥ f (y) for all such x and y. Moreover, a function is monotone if the direction is up
in all dimensions. Thus, unateness is a generalization of monotonicity.
The domain [n]d is called a hypergrid and the special case {0, 1}d is called a hypercube. The
distance between two functions f, g : [n]d → R is equal to the fraction of points x ∈ [n]d where
f (x) 6= g(x). Given a parameter  ∈ (0, 1), two functions f and g are -far from each other
if the distance between f and g is at least . A function f is -far from a property P if it is
-far from any function which has property P . A property tester [10, 16] for a property P is a
randomized algorithm which, given parameter  ∈ (0, 1) and oracle access to the input function
f , accepts f with probability 23 , if it has the property P , and rejects f with probability 32 , if it is
-far from P . A tester is nonadaptive if it makes all queries in advance, and adaptive otherwise.
A testing algorithm for property P has 1-sided error if it always accepts all inputs that satisfy P
and 2-sided error, otherwise. A unateness tester is a property tester for unateness. To the best of
our knowledge, testing unateness has been studied previously only for Boolean functions over the
hypercube domain.
∗
†

This work was partially supported by NSF award CCF-1422975.
Pennsylvania State University, rxb5410@cse.psu.edu, mzm269@psu.edu, rxp271@cse.psu.edu, sofya@cse.psu.edu.

1

1.1

Our results

In this paper, we give a unateness tester for real-valued function over the hypergrid. It is the
first unateness tester for this type of functions. We also present first lower bounds on the number
of queries required to test unateness. In particular, our tester and lower bound differ only by a
logarithmic factor for real-valued functions over the hypercube.
The query complexity of our unateness tester is O( d log(max(d,n))
) for functions f : [n]d → R. Our

tester generalizes the tester of Khot and Shinkar [12] to real-valued functions over the hypergrid
d
domain. Their tester has query complexity O( d log
 ) and it works for Boolean functions over the
hypercube domain.
We also present two lower bounds for testing unateness of functions over the hypercube domain.
The first lower bound of Ω(min{d, |R|2 }), where√R is the range of the function, is over the realvalued functions. Our second lower bound of Ω( d/) is for nonadaptive, 1-sided error unateness
testers over Boolean functions. Our lower bounds build on the same lower bounds for monotonicity
testing by Blais et al. [3] and Fischer et al. [9] of Boolean functions over the hypercube domain.

1.2

Previous work

The problem of testing unateness was first considered by Goldreich et al. [11]. In their work, by
extending their monotonicity tester, they obtain a nonadaptive, 1-sided error tester for unateness
3/2
with query complexity O( d  ). Recently, Khot and Shinkar [12] gave an adaptive unateness tester
d
with query complexity O( d log
 ).
The related property of monotonicity has been studied extensively for different types of functions
in the context of property testing. The problem of testing monotonicity of Boolean functions over
the hypercube domain was first introduced by Goldreich et al. [11]. It was shown in [8, 11] that
monotonicity for hypercube domain can be tested with query complexity O( d ). A monotonicity
7/8
tester with better query complexity of Õ( d3/2 ) was introduced by Chakrabarty and Seshadhri [5].
Chen et al. [6] modified the tester of Chakrabarty and Seshadhri [5] and improved the query
5/6
complexity to Õ( d4 ). Most recently, Khot et al. [13] improved the query complexity of the tester
√

to Õ( 2d ).
The lower bound for any
√ nonadaptive one-sided error tester for monotonicity over the hypercube was proved
to
be
Ω(
d) by Fischer et al. [9]. Also, Chen et al. [7] gave a lower bound
√
of almost Ω( d) for any nonadaptive, two-sided error tester. Moreover, there is a lower bound
of Ω(min{d, |R|2 }) over the real-valued functions by Blais et al. [3]. Most recently, Belovs and
1
Blais [1] gave a lower bound of Ω̃(d 4 ) for adaptive testers of Boolean functions over the hypercube. Chakrabarty and Seshadhri [4] proved that any adaptive, two-sided monotonicity tester for
−1
functions f : [n]d → N must make Ω( d log n−log
) queries.


2

Algorithm for Testing Unateness

In this section, we present an algorithm to test unateness of real-valued functions over the
hypergrid domain and prove Theorem 2.1.
We use the notation z ◦T w to denote concatenation with respect to the locations in the set
T . More specifically, this operation fills the locations in T with |T | bits in z, and the other [d] \ T
locations with d − |T | bits in w, respectively.
Theorem 2.1. For a given function f : [n]d → R, there exists a 1-sided error unateness tester with

2

a query complexity of O( d log(max(d,n))
), where  ∈ (0, 12 ) is the proximity parameter.

Proof. The main idea of the tester described in Algorithm 1 is as follows. Given a function f :
[n]d → R, the tester finds a subset of influential dimensions T ⊆ [d], such that the dependence of
f on the remaining dimensions, [d] \ T , is negligible. Furthermore, for each influential dimension
i ∈ T , the tester finds an edge (x, x + ei ), where f (x) 6= f (x + ei ), and assigns a direction to the i-th
dimension according to the value of f at these two points. The direction is up if f (x) < f (x + ei )
and it is down if f (x) > f (x + ei ). After that, the algorithm applies a monotonicity tester on f
with respect to the directions for the dimensions in T and some random assignments w for other
dimensions, and outputs the answer.
Algorithm 1 Unateness Tester(f : [n]d → R, )
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

Let m = O( d ) and T = ∅
for i = 1...m do
Find an Influential Dimension(f, T )
if it returns a dimension and its direction (i∗ , bi∗ ) then
Add i∗ to T , and let bi∗ be its direction
end if
end for
Pick a uniform w ∈ [n][d]\T
Let fw (z) = f (z ◦T w) for all z ∈ [n]T
Apply the monotonicity tester by Chakrabarty and Seshadhri [4] on fw with respect to the
directions {bi : i ∈ T } and proximity parameter 2
return the output of the monotonicity tester

In order to find influential dimensions, the tester uses the function Find an Influential Dimension,
which is presented in Algorithm 2. It works as a subroutine and tries to find an influential dimension
in each run. It gets oracle access to a function f : [n]d → R, and a subset of dimensions T ⊆ [d],
which is empty at the beginning. This subroutine outputs ⊥ if it doesn’t find any new influential
dimension. Otherwise, it outputs a dimension i∗ ∈ [d] \ T and its direction bi∗ ∈ {up, down}.
This subroutine can find a new influential dimension and its direction with high probability if f
has non-negligible dependence on the dimensions in [d]\T . Each time we run Find an Influential Dimension,
it picks two points x, y ∈ [n]d uniformly and independently at random, whose coordinates are equal
in the dimensions in T . If f (x) 6= f (y), it uses binary search to decrease the distance between x and
y to 1, while ensuring that f (x) 6= f (y) still holds.
If the input function f is unate, then the tester always accepts, as Algorithm 2 always finds
the correct direction for each influential dimension and the function with respect to the influential
dimensions is monotone.
In order to show the correctness of Algorithm 1, we will prove the following two lemmas. In
these lemmas let r denote the number of different values in the image of the function f , and Pkz
where k ∈ [r] and z ∈ [n]T be the fraction of the k th frequent value among the values of f (x|xT =z ).
Lemma 2.2. Let f : [n]d → R and T ⊆ [d] be the set in Algorithm 1 after running m = O( d )
iterations of Algorithm 2. Then, with probability at least 5/6, the set T satisfies
" r
#
X

Ez∈[n]T
Pkz (1 − Pkz ) < .
16
k=1

3

Algorithm 2 Find an Influential Dimension(f : [n]d → R, T )
1:
2:
3:
4:
5:
6:
7:
8:
9:

Pick x, y ∈R [n]d independently and uniformly at random such that xT = yT
if f (x) = f (y) then
return ⊥
else
do
U ← {i ∈ [d] : xi = yi }
V ← {i ∈ [d] : xi 6= yi }
Let V = {v1 , ..., vt }
Set zV = xv1 ◦ ... ◦ xvb t c ◦ yvb t c+1 ◦ ... ◦ yvt
2

10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:

2

Let z = xU ◦T zV ∈ [n]d
if f (x) 6= f (z) then
y←z
else
x←z
end if
while |V | =
6 1
Let i∗ ∈ [d] be the element in V
Let b ∈ {up, down} be the direction of edge (x, y)
return (i∗ , b)
end if

Lemma 2.3. Let f : [n]d → R be a real-valued function, and let T ⊆ [d] such that,
#
" r
X

z
z
Ez∈[n]T
Pk (1 − Pk ) < .
16

(1)

k=1

Then, for a random w ∈ [n][d]\T ,
Pr
w∈[n][d]\T


1
[dist(fw , f ) > ] ≤ .
2
6


Proof of Lemma 2.2. First, we show that Ez∈[n]T

r
P
k=1

Pkz (1



−

Pkz )

is equal to the probability that

Algorithm 2 finds a new dimension on input (f, T ). Algorithm 2 finds a new dimension if and only
if f (x) 6= f (y) in Line 2. By definition of Pkz , the probability of choosing x such that f (x) = k
is Pkz , and the probability of choosing y such that f (y) 6= k is 1 − Pkz . The total probability of
r
P
choosing two different values is
Pkz (1 − Pkz ) for a fixed z. So, the probability over all possible
 r
 k=1
P z
z
z’s is Ez∈[n]T
Pk (1 − Pk ) .
i=1

Now, we state the following
claim to prove that when the Algorithm 2 finds a new dimension
 r
P z
then the value of Ez∈[n]T
Pk (1 − Pkz ) does not increase.
k=1

4

Claim 2.4. For ∀T ⊆ [d] and ∀i ∈ [d], when the dimension i is added to the set T , the value of
" r
#
X
Ez∈[n]T
Pkz (1 − Pkz )
k=1

does not increase.
z
Proof. Let Pk,T
denote Pkz when z ∈ [n]T . Let T 0 = T ∪ {i}. Define zj , to be equal to z for all
dimensions in T , and equal to j in the ith dimension, for each j ∈ [n]. To simplify notation for the
n
P
Pj
z , P j = P zj , for j ∈ [n]. Then, P =
rest of the proof, let P = Pk,T
0
k,T
n . The probability that
j=1

Algorithm 2 finds a new dimension on input (f, T 0 ) is


r X
n
j
j
X
P (1 − P ) 
.
Ez∈[n]T 
n
k=1 j=1

n
P

To complete the proof, it is enough to show that g(P ) ≥

j=1

inequality holds because P =

n
P
j=1

Pj
n

g(P j )
n ,

where g(x) = x(1 − x). This

and g is concave.

The following claim completes the proof of Lemma 2.2.
Claim 2.5. After m = O( d ) iterations of Algorithm 2, either the size of the set T is equal to d, or
with probability at least 5/6, the following inequality holds,
#
" r
X

z
z
Ez∈[n]T
Pk (1 − Pk ) < .
16
k=1

Proof. Let Yi be an indicator random variable, which is equal to 1 if Algorithm 2 finds

 r a new dimenP z
z
th
sion in the i iteration and 0, otherwise. We have Pr[Yi ] = Ez∈[n]Ti [Yi ] = Ez∈[n]Ti
Pk (1 − Pk ) ,
k=1

where Ti is the set of influential dimensions in the ith iteration. Hence, the total number of dim
P
mensions that Algorithm 2 finds after m iterations is Y =
Yi . Now, after m iterations, if the
i=1

following holds:
Ez∈[n]T

" r
X

#
Pkz (1 − Pkz ) ≥

k=1

then,
Ez∈[n]|T | [Y ] ≥
Using Chernoff Bound we have,
Pr [Y ≤

z∈[n]T

For m =

32d


m
.
16

m
m
] ≤ e− 128 .
32

and d ≥ 8, we have
d
1
Pr [Y ≤ d] ≤ e− 4 ≤ .
T
6
z∈[n]

5


,
16

This completes the proof of Lemma 2.2.
Proof of Lemma 2.3. Define the plurality function PlT : [n]T → [r] as PlT (z) = k such that Pkz is
the maximum (ties are broken arbitrarily).
By assumption (1) for a uniformly random w ∈ [n][d]\T , it holds that


Ew∈[n][d]\T [dist(fw , PlT )] = Ew∈[n][d]\T
Pr [fw (z) 6= PlT (z)]
z∈[n]T
h
i
= Ew∈[n][d]\T Ez∈[n]T [1(fw (z) 6= PlT (z))]
h
i
= Ez∈[n]T Ew∈[n][d]\T [1(fw (z) 6= PlT (z))]


= Ez∈[n]T
Pr [fw (z) 6= PlT (z)] .
w∈[n][d]\T

Without loss of generality, assume that P1z is the probability of the value with the highest
frequency in f (x|xT =z ). Hence,


Ez∈[n]T
Pr [fw (z) 6= PlT (z)] = Ez∈[n]T [1 − P1z ].
w∈[n][d]\T

Claim 2.6. For all z ∈ [n]T ,
1 − P1z ≤

r
X

Pkz (1 − Pkz ).

k=1

Proof. To simplify notations for the rest of the proof, let Pk = Pkz . We have
r
X

Pk (1 − Pk ) = 1 −

k=1

r
X

Pk2 .

k=1

So it is enough to show that, 1 − P1 ≤ 1 −

r
P
k=1

r
X
P2
k

k=1

P1

Pk2 or

≤

r
P
k=1

r
X
P2
k

k=1

Pk

Pk2 ≤ P1 which can be proved as follows,

=1

By Claim 2.6 and our initial assumption (1), we have
" r
#
X

z
z
z
Ez∈[n]T [1 − P1 ] ≤ Ez∈[n]T
Pk (1 − Pk ) < .
16
k=1

So,
Ew∈[n][d]\T [dist(fw , PlT )] <
6


.
16

By Markov’s inequality,

Pr
w∈[n][d]\T


1
3
≤ .
dist(fw , PlT ) ≥
8
6

Moreover,
dist(f, PlT ) = Ew∈[n][d]\T [dist(fw , PlT )] <


.
16

Therefore, by triangle inequality we have,


3
1

7
Pr
dist(f (x|x[d]\T =w ), f ) ≥
≤ .
+ ]≤
Pr [dist(fw , PlT ) ≥
[d]\T
[d]\T
8
16
16
6
w∈[n]
w∈[n]
This completes the proof of Lemma 2.3.
The proof of Theorem 2.1 follows from Lemmas 2.2 and 2.3. Let T ⊆ [d] be the set of influential
dimensions in the unateness tester after m = O( d ) iterations of Algorithm 2. By Lemma 2.2 the
following inequality holds with probability at least 5/6
" r
#
X

z
z
Ez∈[n]T
Pk (1 − Pk ) < .
16
k=1

If T satisfies the above inequality and f is -far from being unate, then by Lemma 2.3, for a
random w ∈ [n][d]\T , the function f (x|x[d]\T =w ) is 2 -far from being unate with probability at least
5

6 . And with the same probability it is 2 -far from being monotone with respect to the directions
of dimensions in the set T . So, with high probability the monotonicity tester in Algorithm 1 will
reject f (x|x[d]\T =w ) with respect to the directions of the dimensions in T .
Now, we analyze the query complexity of Algorithm 1. Each call of Algorithm 2 makes O(log d)
queries to perform the binary search. Algorithm 2 is called O( d ) times by Algorithm 1. At the
n
end, Algorithm 1 runs monotonicity tester with query complexity O( d log
 ). So, the total query
complexity of Algorithm 1 is O( d log(max(d,n))
).

This completes the proof of Theorem 2.1.

3
3.1

Lower Bounds for Unateness
Lower Bound for Real-Valued Functions

In this section, we prove an adaptive, 2-sided error lower bound for testing unateness of functions
over the hypergrid domain. This lower bound technique builds on the one used for proving the
lower bound for monotonicity by Blais et al. [3].
Theorem 3.1. Testing f : {0, 1}d → R for unateness requires Ω(min{d, |R|2 }) queries.
Proof. First, we consider the case when R = R. We will prove the lower bound for testing unateness
in this case by a reducton from Set-Disjointness problem.
Definition 3.1. (Set-Disjointness) In the Set-Disjointness problem, there are two players Alice and
Bob. Alice receives a string S as input and Bob receives a string T as input, where both strings
have size k. Alice and Bob also have access to a random string. They must compute the value of
function DISJk (S, T ), which is 1 if S ∩ T = ∅ and 0 otherwise.
7

Theorem 3.2. Testing f : {0, 1}d → R for unateness requires Ω(d) queries.
Proof. Let S, T ⊆ [d] be the subsets received by Alice and Bob as the input to an instance of the
Set-Disjointness problem.
Alice and Bob buildP functions χS , χT : {0, 1}d → {−1, 1}, respectively,
P
where χS (x) = (−1) i∈S xi and χT (x) = (−1) i∈T xi . Let h : {0, 1}d → Z be a function defined by
h(x) = 2|x| + χS (x) + χT (x).
Claim 3.3. The following holds:
(a) The function h is unate if S and T are disjoint.
(b) The function h is 18 -far from unate, otherwise.
Proof. Fix i ∈ [d]. For every x ∈ {0, 1}d , we define x0 , x1 ∈ {0, 1}d to be the vectors obtained by
fixing the ith coordinate of x to 0 and 1, respectively.
Fist, we prove part (a). Since S and T are disjoint, there are three cases:
1. i ∈
/ S and i ∈
/ T . Then,
h(x1 ) − h(x0 ) = 2|x1 | − 2|x0 | = 2 > 0.
2. i ∈ S and i ∈
/ T . Then,
h(x1 ) − h(x0 ) = 2|x1 | − 2|x0 | − 2χS (x0 ) ≥ 0.
3. i ∈
/ S and i ∈ T . Then,
h(x1 ) − h(x0 ) = 2|x1 | − 2|x0 | − 2χT (x0 ) ≥ 0.
So, when S and T are disjoint, the function h is non-decreasing along dimension i.
For the part (b) of our claim, since S ∩ T 6= φ there exists i ∈ S ∩ T . For this i, we will show that
there exists 41 -fraction of pairs of the form (x0 , x1 ) such that h(x1 ) < h(x0 ) and another 41 -fraction
of pairs such that h(x1 ) > h(x0 ) implying that h is not unate. We have
h(x1 ) − h(x0 ) = 2|x1 | − 2|x0 | − 2χS (x0 ) − 2χT (x0 ).
It is clear that if χS (x0 ) = χT (x0 ) = 1 then h(x1 ) < h(x0 ). And if χS (x0 ) = χT (x0 ) = −1
then h(x1 ) > h(x0 ). Suppose that j ∈ S and also j 6= i. Let x̄0 be x0 with the j th bit flipped.
Then, χS (x0 ) = −χS (x̄0 ) , which means χS (x0 ) = 1 with probability 21 . By the same argument,
χT (x0 ) = 1 with probability 21 . So, at least for 14 of these pairs we have χS (x0 ) = χT (x0 ) = 1.
By using the same technique we can prove that for at least 41 fraction of these pairs we have
χS (x0 ) = χT (x0 ) = −1. Therefore, when S and T are overlapping, h is 81 -far from unate.
This completes the proof of Theorem 3.2
√
Now consider the case when |R| > 12 d + 5. We can again use a reduction from set-disjointness
problem.
√
Theorem 3.4. Testing f : {0, 1}d → R for unateness, where |R| > 12 d+5, requires Ω(d) queries.

8

√
√
Proof. Without lost of generality we can also assume that {d − 6 d − 2, ..., d + 6 d + 2} ⊆ R. Let
χS , χT : {0, 1}d → {−1, 1} be the functions given to Alice and Bob in the communication game,
where S, T ⊆ [d]. Now we will define the function h0 : {0, 1}d → Z (as defined in [3]), as follows:

√
√
d

d − 6√d − 2 if |x| < 2 − 3√d;
h0 (x) = d + 6 d + 2 if |x| > d2 + 3 d;


h(x)
otherwise.
√
This function rounds
h(x) up to d − 6 d − 2 for strings with low Hamming distance and rounds
√
h(x) down to d + 6 d + 2 for strings
with high Hamming
distance. It also keeps the actual value
√
√
of h for points x such that d2 − 3 d ≤ |x| ≤ d2 + 3 d. By the definition of h(x), this value will be
√
√
between d − 6 d − 2 and d + 6 d + 2.
Claim 3.5. Function h0 is unate if h is unate and h0 is 1/16-far from unate when h is 1/8-far from
unate.
Proof. Since every monotone function is also unate, the first part of the claim directly follows from
Blais et al. [3].
1
For the second part we prove that the distance between h and h0 is at most 16
. Thus, when S
1
1
0
and T intersect, h is 8 -far from unate and so h is 16 -far from unate. Let x be a uniformly random
√
√
point from {0, 1}d . We know that h0 (x) = h(x) when d2 − 3 d ≤ |x| ≤ d2 + 3 d. By Chernoff
Bound,


√
1
1
d
> 3 d < 0.03 <
⇒ Pr[h0 (x) 6= h(x)] < .
Pr |x| −
2
16
16
By triangle inequality, h0 is at least

1
16 -far

from unate.

This completes the proof of Theorem 3.4.
For the last case, we prove the following theorem.

√
Theorem 3.6. Testing a function f : {0, 1}d → R for unateness, where |R| = o( d), requires
Ω(|R|2 ) queries.
Proof. In this case, we can prove the lower bound by using a reduction to Theorem 3.4. Let m be
√
the largest integer such that |R| > 12 m + 5. We prove the following claim.
Claim 3.7. For every function g : {0, 1}m → R, there exists a function h : {0, 1}d → R satisfying
the following conditions:
1. If g is unate, then h is also unate.
2. If g is -far from unate, then h is also -far from unate.
3. For all x ∈ {0, 1}d , we can find h(x) with one query to g.

9

Proof. We use padding technique to construct h from g. Let h(x, y) = g(x) where x ∈ {0, 1}m and
y ∈ {0, 1}d−m . The first and third conditions can be directly deduced from the definition of h. For
the second condition, suppose, for the sake of contradiction that h is -close from unate. Then,
there exists a unate function h̃, such that Prx,y [h̃(x, y) 6= h(x, y)] < . By an averaging argument,
we can find a ỹ ∈ {0, 1}d−m where, Prx [h̃(x, ỹ) 6= h(x, ỹ)] < . Now, let g̃(x) = h̃(x, ỹ) for all
x ∈ {0, 1}m . Thus, g̃ is unate and Prx [g̃(x) 6= g(x)] < , contradicting the assumption that g is
-far from unate.
Now we can construct a tester for a given input g : {0, 1}m → R. Suppose, h is the function
that satisfies Claim 3.7. We run the unateness tester on h and output its answer. By Claim 3.7,
correctness of this tester follows from the correctness of the tester for h. Since in Theorem 3.4
we proved that the unateness tester for g uses Ω(m) queries and Claim 3.7 condition 3 holds, the
tester for h uses the same√number of queries. This means testing a function f : {0, 1}d → R for
unateness, where |R| = o( d), requires Ω(m) = Ω(|R|2 ) queries.
Theorem 3.1 follows from Theorems 3.2, 3.4 and 3.6.

3.2

Lower Bound for Boolean Functions

In this section, we prove a nonadaptive, 1-sided error lower bound for testing unateness of
Boolean functions over the hypercube domain. This lower bound technique is similar to the one
used for proving the lower bound for monotonicity by Fischer et al. [9].
Theorem 3.8. Every nonadaptive
√ 1-sided error tester for unateness of functions of the form f :
d
{0, 1} → {0, 1} must make Ω( d) queries.
The proof of the theorem is by the application of Yao’s minimax principle. A 1-sided error tester
must reject only if it finds a violation, otherwise it must accept. We define a distribution over a
set of “hard” functions and prove that for this hard
√ distribution, a tester with query complexity q
detects a violation with probability at most O(q/ d).
For x ∈ {0, 1}d , define |x| as the
of bits that are equal to 1. The set of hard functions
 number

is defined as follows: for every i ∈ d2 , define fi : {0, 1}d → {0, 1} as


1
fi (x1 , . . . , xd ) = 0


xi ⊕ xi+ d

√
if |x| > d/2 + d
√
if |x| < d/2 − d
otherwise

2

Claim 3.9. For every i ∈

d
2

, fi is -far from unate for some constant  such that 0 <  ≤ 41 .

 
th
Proof. For a fixed i ∈ d2 , group together all points that differ only in the ith and i + d2
coordinate. There are 4 points in each group as illustrated in Figure 3.1. Overall, there are 2d−2
such independent groups.
It can be seen that a constant fraction of such groups violate unateness of fi (by its definition).
In each such group, the value of fi on at least 1 point has to be changed (or “repaired”) to make it
unate. Thus, overall, a constant fraction of points have to be changed to make the function unate.
Hence, fi is -far from unate for some constant .

10

Figure 3.1: Illustration of “hard” function
Proof of Theorem 3.8. Let Q be the queried set of points from {0, 1}d of size q. By the definition
of 1-sided error tester, we need to sample at least one violated, comparable pair of points to reject
the function (A pair of points (x, y) is comparable if either x ≺ y or y ≺ x). So, the tester can
detect a violated pair for fi if there exists two queries u, v such that they are comparable and differ
th
in either ith or i + d2
coordinate. Construct an undirected graph with vertex set Q and edge
set {(x, y)|x and y are comparable, x, y ∈ Q}. Consider a spanning forest of this graph. If there
exists a violation by function fi in pair (u, v) they should be in the same tree. Moreover, there
should exist an adjacent pair of vertices in the path between u and v which differ in the ith bit.
Therefore, the total number of functions fi for which the query set could find the violation is at
most the maximum number of edges in the spanning forest (which is at most
√ q − 1) times the
maximum possible distance between two adjacent vertices (which is at√most 2 d with respect
to
√
our function√because all violations are for x ∈ {0, 1}d such that d/2 − d ≤ |x| ≤ d/2 + d). So
at most O(q d) functions can be detected for violation. We have d2 different functions. Hence, the
√
number of queries required is at least Ω( d).

4

Open Questions

Our bounds for testing unateness are nearly tight for real-valued functions. However, there is a
gap between the upper and lower bounds for Boolean functions. The first open question is to close
this gap. In this paper, we consider testing unateness of real-valued functions with respect to the
Hamming distance. Can one design testers with respect to other metrics such as Lp -distances, as
defined in [2]?

References
[1] Aleksandrs Belovs and Eric Blais. A polynomial lower bound for testing monotonicity. In
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC
2016, Cambridge, MA, USA, June 18-21, 2016, pages 1021–1032, 2016.
[2] Piotr Berman, Sofya Raskhodnikova, and Grigory Yaroslavtsev. Lp -testing. In Symposium
on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages
164–173, 2014.
[3] Eric Blais, Joshua Brody, and Kevin Matulef. Property testing lower bounds via communication complexity. Computational Complexity, 21(2):311–358, 2012.
[4] Deeparnab Chakrabarty and C Seshadhri. Optimal bounds for monotonicity and lipschitz test-

11

ing over hypercubes and hypergrids. In Proceedings of the forty-fifth annual ACM symposium
on Theory of computing, pages 419–428. ACM, 2013.
[5] Deeparnab Chakrabarty and C. Seshadhri. A o(n) monotonicity tester for boolean functions
over the hypercube. In Symposium on Theory of Computing Conference, STOC’13, Palo Alto,
CA, USA, June 1-4, 2013, pages 411–418, 2013.
[6] Xi Chen, Rocco A. Servedio, and Li-Yang Tan. New algorithms and lower bounds for monotonicity testing. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS
2014, Philadelphia, PA, USA, October 18-21, 2014, pages 286–295, 2014.
[7] Xi Chen, Anindya De, Rocco A. Servedio, and Li-Yang Tan. Boolean function monotonicity
testing requires (almost) n1/2 non-adaptive queries. In Proceedings of the Forty-Seventh Annual
ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17,
2015, pages 519–528, 2015.
[8] Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, and Alex
Samorodnitsky. Improved testing algorithms for monotonicity. In Randomization, Approximation, and Combinatorial Algorithms and Techniques, Third International Workshop on
Randomization and Approximation Techniques in Computer Science, and Second International
Workshop on Approximation Algorithms for Combinatorial Optimization Problems RANDOMAPPROX’99, Berkeley, CA, USA, August 8-11, 1999, Proceedings, pages 97–108, 1999.
[9] Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, and Alex
Samorodnitsky. Monotonicity testing over general poset domains. In Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada,
pages 474–483, 2002.
[10] Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to
learning and approximation. Electronic Colloquium on Computational Complexity (ECCC), 3
(57), 1996.
[11] Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, and Alex Samorodnitsky. Testing
monotonicity. Combinatorica, 20(3):301–337, 2000.
e
[12] Subhash Khot and Igor Shinkar. An O(n)
queries adaptive tester for unateness. RANDOM,
2016.
[13] Subhash Khot, Dor Minzer, and Muli Safra. On monotonicity testing and boolean isoperimetric
type theorems. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS
2015, Berkeley, CA, USA, 17-20 October, 2015, pages 52–58, 2015.
[14] Yue-Sun Kuo and WK Chou. Generating essential primes for a boolean function with multiplevalued inputs. In Proceedings of the 23rd ACM/IEEE Design Automation Conference, pages
193–199. IEEE Press, 1986.
[15] Alan Mishchenko. Introduction to zero-suppressed decision diagrams. Applications of ZeroSuppressed Decision Diagrams, 2014.

12

[16] Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications
to program testing. SIAM J. Comput., 25(2):252–271, 1996.
[17] Tsutomu Sasao. Switching theory for logic synthesis. Springer Science & Business Media, 2012.

13

