Erasure-Resilient Property Testing∗
Kashyap Dixit†

Sofya Raskhodnikova†

Abhradeep Thakurta‡

Nithin Varma†

arXiv:1607.05786v1 [] 20 Jul 2016

Abstract
Property testers form an important class of sublinear algorithms. In the standard property testing
model, an algorithm accesses the input function f : D 7→ R via an oracle. With very few exceptions, all
property testers studied in this model rely on the oracle to provide function values at all queried domain
points. However, in many realistic situations, the oracle may be unable to reveal the function values at
some domain points due to privacy concerns, or when some of the values get erased by mistake or by an
adversary. The testers do not learn anything useful about the property by querying those erased points.
Moreover, the knowledge of a tester may enable an adversary to erase some of the values so as to increase
the query complexity of the tester arbitrarily or, in some cases, make the tester entirely useless.
In this work, we initiate a study of property testers that are resilient to the presence of adversarially
erased function values. An α-erasure-resilient ε-tester is given parameters α, ε ∈ (0, 1), along with oracle
access to a function f such that at most an α fraction of function values have been erased. The tester does
not know whether a value is erased until it queries the corresponding domain point. The tester has to
accept with high probability if there is a way to assign values to the erased points such that the resulting
function satisfies the desired property P. It has to reject with high probability if, for every assignment
of values to the erased points, the resulting function has to be changed in at least an ε-fraction of the
non-erased domain points to satisfy P.
We design erasure-resilient property testers for a large class of properties. For some properties, it is
possible to obtain erasure-resilient testers by simply using standard testers as a black box. However, there
are more challenging properties for which all known testers rely on querying a specific point. If this point
is erased, all these testers break. We give efficient erasure-resilient testers for several important classes
of such properties of functions including monotonicity, the Lipschitz property, and convexity. Finally, we
show a separation between the standard and erasure-resilient testing. Specifically, we describe a property
that can be ε-tested with O(1/ε) queries in the standard model, whereas testing it in the erasure-resilient
model requires number of queries polynomial in the input size.

1

Introduction

In this paper, we revisit the question of how sublinear-time algorithms access their input. With very few
exceptions, all algorithms studied in the literature on sublinear-time algorithms have oracle access to their
input1 . However, in many applications, this assumption is unrealistic. The oracle may be unable to reveal
parts of the data due to privacy concerns, or when some of the values get erased by mistake or by an
adversary. Motivated by these scenarios, we propose to study sublinear algorithms that work with partially
erased data.
∗ A preliminary version of this work will appear in the Proceedings of the International Colloquium on Automata, Languages
and Programming 2016 [DRTV16].
† Department of Computer Science and Engineering, The Pennsylvania State University. These three authors were supported
in part by NSF award CCF-1320814, NSF CAREER award CCF-0845701, NSF award CCF-1422975, Pennsylvania State
University College of Engineering Fellowship and Pennsylvania State University Graduate Fellowship. (kashyap@cse.psu.edu,
sofya@cse.psu.edu, nzm154@psu.edu).
‡ Previously at Yahoo Labs. guhathakurta.abhradeep@gmail.com
1 Sublinear-time algorithms with various distributional assumptions on the positions of the input the algorithms access have
been investigated, for example, in [GGR98, BBBY12, GR16]. There is also a line of work, initiated by [BFR+ 13], that studies
sublinear algorithms that access distributions, as opposed to fixed datasets. In this work, we focus on fixed datasets.

1

Formally, we view a dataset as a function over some discrete domain D, such as [n] = {1, . . . , n} or [n]d .
For example, the classical problem of testing whether a list of n numbers is sorted in nondecreasing order
can be viewed as a problem of testing whether a function f : [n] → R is monotone (nondecreasing). Given
a parameter α ∈ (0, 1), we say that a function is α-erased if at most an α fraction of its domain points
are marked as “erased” or protected (that is, an algorithm is denied access to these values). An algorithm
that takes an α-erased function as its input does not know which values are erased until it queries the
corresponding domain points. For each queried point x, the algorithm either learns f (x) or, if x is an erased
point, gets back a special symbol ⊥. We study algorithms that work in the presence of adversarial erasures.
In other words, the query complexity of an algorithm is the number of queries it makes in the worst case
over all α-erased input functions.
In this work, we initiate a systematic study of property testers that are resilient to the presence of
adversarial erasures. An α-erasure-resilient ε-tester is given parameters α, ε ∈ (0, 1), along with oracle access
to an α-erased function f . The tester has to accept with high probability if f can be restored to a function on
the whole domain that satisfies the desired property P and reject with high probability if every restoration
of f is ε-far from P on the nonerased part of the domain. This generalizes the standard property testing
model of Rubinfeld and Sudan [RS96] and Goldreich, Goldwasser and Ron [GGR98] .
Generic transformations Our first goal is to understand which existing algorithms in the standard property testing model can be easily made erasure-resilient. We show (in Section 2) how to obtain
erasure-resilient testers for some properties by using standard testers for these properties as black box.
Our transformations apply to testers that query uniformly and independently sampled points, with some
additional restrictions. More specifically, our transformations work for uniform proximity oblivious testers
(POTs) [GR11] and uniform testers for extendable properties. As a result, we are able to obtain erasureresilient testers for being a low-degree polynomial [RS96], monotonicity over general poset domains [FLN+ 02],
convexity of black and white images [BMR15], and Boolean functions over [n] having k runs of 0s and 1s.
Erasure-resilient testers for more challenging properties One challenge in designing erasureresilient testers by using existing algorithms in the standard model as a starting point is that many existing
algorithms are more likely to query certain points in the domain. Therefore, if these points are erased, the
algorithms break. Specifically, the optimal algorithms for testing whether a list of numbers is sorted (and
there are at least three different algorithms for this problem [EKK+00, BGJ+ 12, CS13]) have this feature.
Moreover,
it is known that an algorithm that makes uniformly random queries is far from optimal: it needs
√
Θ( n) queries instead of Θ(log n) for n-element lists [EKK+ 00, Fis04].
There is a number of well studied properties for which all known optimal algorithms heavily rely on
querying specific points. Most prominent examples include monotonicity, the Lipschitz properties and, more
generally, bounded-derivative properties of real-valued functions on [n] and [n]d , as well as convexity of realvalued functions on [n]. It is especially challenging to deal with real-valued functions in our model, because
there are many possibilities for erased values. We give efficient erasure-resilient testers for all aforementioned
properties of real-valued functions in Sections 3-6.
Relationships to other models We explore the relationship of erasure-resilient testing with other
testing models in Section 7. We provide (in Section 7.1) a separation between our erasure-resilient model
and the standard model. Specifically, we prove the existence of a property that can be tested with O(1/ε)
queries in the standard model, but requires polynomially many queries in the length of the input in the
erasure-resilient model. This result builds on the ideas of Fischer and Fortnow [FF06] that separate tolerant
testing, defined by Parnas, Ron and Rubinfeld [PRR06], from standard testing.
A tolerant tester for a property P, given two parameters ε1 , ε2 ∈ (0, 1), where ε1 < ε2 , is required to,
with probability at least 2/3, accept inputs that are ε1 -close to P and reject inputs that are ε2 -far from
P. Intuitively, the relationship of our erasure-resilient model to tolerant testing is akin to the relationship
between error-correcting codes that withstand erasures and error-correcting codes that withstand general
errors. As shown in [PRR06], tolerant testing is equivalent to approximating the distance of a given input
2

to the desired property. In Section 7.2, we prove that the existence of tolerant testers implies the existence
of erasure-resilient testers with related parameters. Using this implication and existing tolerant testers
for sortedness [SS10], monotonicity [FR10], and convexity [FR], we get erasure-resilient testers for these
properties as corollaries. However, we obtain erasure-resilient testers for these properties with much better
parameters in the technical sections of this article. We conjecture that erasure-resilient testing can be
separated from tolerant testing in the same strong sense as in our separation of standard testing from
erasure-resilient testing.

1.1

The Erasure-Resilient Testing Model

We formalize our erasure-resilient model for the case of property testing. Erasure-resilient versions of other
computational models, such as tolerant testing, can be defined analogously.
Definition 1.1 (α-erased function). Let D be a domain, R be a range, and α ∈ (0, 1). A function2
f : D 7→ R ∪ {⊥} is α-erased if f evaluates to ⊥ on at most an α fraction of domain points. The points on
which f evaluates to ⊥ are called erased. The set of remaining (nonerased) points is denoted by N .
A function f is ε-far from a property (set) P if it needs to be changed on at least an ε fraction of domain
points to obtain a function in P. A function f ′ : D → R that differs from a function f only on points erased
in f is called a restoration of f .
Definition 1.2 (Erasure-resilient tester). An α-erasure-resilient ε-tester of property P gets input parameters
α, ε ∈ (0, 1) and oracle access to an α-erased function f : D → R ∪ {⊥}. It outputs, with probability3 at
least 2/3,
• accept if there is a restoration f ′ : D → R of f that satisfies P;
• reject if every restoration f ′ : D → R of f needs to be changed on at least an ε fraction of N , the
|
nonerased portion of f ’s domain, to satisfy P (that is, f ′ is ε · |N
|D| -far from P).
The tester has 1-sided error if the first item holds with probability 1.
Let f|N denote the function f restricted to the set N of nonerased points. We show (in Section 2) that if
property P is extendable, we can define a property PN such that the erasure-resilient tester is simply required
to distinguish the case that f|N satisfies PN from the case that it is ε-far from satisfying it. For example,
if P is monotonicity of functions on a partially-ordered domain D then PN is monotonicity of functions
on N . (Most of the properties we consider in this article, including monotonicity, Lipschitz properties and
convexity, are extendable properties.) Note that, even for the case of extendable properties, our problem
is different from the standard property testing problem because the tester does not know in advance which
points are erased.

1.2

Properties We Consider

Next we define properties of real-valued functions considered in this article and summarize previous work
on testing them. Most properties of real-valued functions studied in the property testing framework are for
functions over the line domain [n] and, more generally, the hypergrid domain [n]d .
Definition 1.3 (Hypergrid, line). Given n, d ∈ N, the hypergrid of size n and dimension d is the set [n]d
associated with an order relation , such that x  y for all x, y ∈ [n]d iff xi ≤ yi for all i ∈ [d], where xi
(respectively yi ) denotes the ith coordinate of x (respectively, y). The special case [n] is called a line.
We consider domains that are subsets of [n]d to be able to handle arbitrary erasures on [n]d .
2 Any object can be viewed as a function. E.g., an n-element array of real numbers can be viewed as a function f : [n] → R,
an image—as a map from the plane to the set of colors, and a graph—as a map from the set of vertex pairs to {0, 1}.
3 In general, the error probability can be any δ ∈ (0, 1). For simplicity, we formulate our model and the results with δ = 1/3.
To get results for general δ, by standard arguments, it is enough to multiply the complexity of an algorithm by log 1/δ.

3

Monotonicity Monotonicity of functions, first studied in the context of property testing in [GGL+ 00],
is one of the most widely investigated properties in this model [EKK+ 00, DGL+ 99, LR01, FLN+ 02, AC06,
Fis04, HK08, BRW05, PRR06, ACCL07, BGJ+ 12, BCGM12, BBM12, CS13, CS14, BRY14, CDJS15]. A
function f : D 7→ R, defined on a partially ordered domain D with order , is monotone if x  y implies
f (x) ≤ f (y) for all x, y ∈ D. The query complexity of testing monotonicity of functions f : [n] 7→ R is
Θ(log n/ε) [EKK+ 00, Fis04]; for functions f : [n]d 7→
p R, it is Θ(d log n/ε) [CS13, CS14], and for functions
over arbitrary partially ordered domains D, it is O( |D|/ε) [FLN+ 02].
Lipschitz properties Lipschitz continuity is defined for functions between arbitrary metric spaces,
but was specifically studied for real-valued functions on hypergrid domains [JR13, AJMR16, CS13, DJRT13,
BRY14, CDJS15] because of applications to privacy [JR13, DJRT13]. For D ⊆ [n]d and c ∈ R, a function
f : D 7→ R is c-Lipschitz if |f (x)−f (y)| ≤ c·||x−y||1 for all x, y ∈ D, where ||x−y||1 is the L1 distance between
x and y. More generally, f is (α, β)-Lipschitz, where α < β, if α · ||x − y||1 ≤ |f (x) − f (y)| ≤ β · ||x − y||1
for all x, y ∈ [n]d . All (α, β)-Lipschitz properties can be tested with O(d log n/ε) queries [CS13].
Bounded derivative properties (BDPs) The class of BDPs, defined by Chakrabartyet al. [CDJS15],
is a natural generalization of monotonicity and the (α, β)-Lipschitz properties. An ordered set B of 2d
functions l1 , u1 , l2 , u2 , . . . , ld , ud : [n − 1] 7→ R ∪ {±∞} is a bounding family if for all r ∈ [d] and y ∈ [n − 1],
lr (y) < ur (y). Let B be a bounding family of functions and let er be the unit vector along dimension r.
The property P(B) of being B-derivative bounded is the set of functions f : [n]d 7→ R such that lr (xr ) ≤
f (x + er ) − f (x) ≤ ur (xr ) for all r ∈ [d] and x ∈ [n]d with xr 6= n, where xr is the rth coordinate of x. The
class of BDPs includes monotonicity and the c-Lipschitz property. The bounding family for monotonicity
is obtained by setting lr (y) = 0 and ur (y) = ∞ for all r ∈ [d], and for the c-Lipschitz property, by setting
lr (y) = −c and ur (y) = c for all r ∈ [d]. In general, different bounding families allow a function to be
monotone in one dimension, c-Lipschitz in another dimension and so on. Chakrabarty et al. [CDJS15]
showed that the complexity of testing BDPs of functions f : [n]d 7→ R is Θ(d log n/ε). A bounding family
B = {l1 , u1 , . . . , ld , ud } defines a quasi-metric
mB (x, y) :=

X

xX
r −1

r:xr >yr t=yr

ur (t) −

X

yX
r −1

lr (t)

r:xr <yr t=xr

over points x, y ∈ [n]d . In [CDJS15], the authors observe that for D = [n]d , a function f : D 7→ R ∈ P(B), the
bounded derivative property defined by B, iff ∀x, y ∈ D, f (x)−f (y) ≤ mB (x, y). We use this characterization
as our definition of BDPs for functions over arbitrary D ⊆ [n]d .
Convexity of functions A function f : D 7→ R is convex if f (tx + (1 − t)y) ≤ tf (x) + (1 − t)f (y) for
(y)
(x)
≤ f (z)−f
for all x < y < z.
all x, y ∈ D and t ∈ [0, 1]. If D ⊆ [n], equivalently, f is convex if f (y)−f
y−x
z−y
Parnas, Ron and Rubinfeld [PRR03] gave a convexity tester for functions f : [n] 7→ R with query complexity
O(log n/ε). Blais, Raskhodnikova and Yaroslavtsev [BRY14] gave an Ω(log n) bound for nonadaptive testers
for this problem.

1.3

Our Results

We give efficient erasure-resilient testers for all properties discussed in Section 1.2. All our testers have
optimal complexity for the case with no erasures and have an additional benefit of not relying too heavily
on the value of the input function at any specific point.
Monotonicity on the line We start by giving (in Section 3) an erasure-resilient monotonicity tester
on [n].

4

Theorem 1.4 (Monotonicity tester on the line). There exists a one-sided error α-erasure-resilient ε-tester
formonotonicity
of real-valued functions on the line [n] that works for all α, ε ∈ (0, 1), with query complexity

log n
O ε(1−α) .
Without erasure resilience, the complexity of testing monotonicity of functions f : [n] 7→ R is Θ(log n/ε)
[EKK+ 00, Fis04]. Thus, the query complexity of our erasure-resilient tester has optimal dependence on the
domain size and on ε.
The starting point of our algorithm is the tester for sortedness from [EKK+ 00]. This tester picks a
random element of the input array and performs a binary search for that element. It rejects if the binary
search does not lead to the right position. The first challenge is that the tester always queries the middle
element of the array and is very likely to query other elements that are close to the root in the binary search
tree. So, it will break if these elements are erased. To make it resilient to erasures, we randomize the binary
tree with respect to which it performs the binary search. The second challenge is that the tester does not
know which points are erased. To counteract that, our tester samples points from appropriate intervals until
it encounters a nonerased point.
To analyze the tester, we bound the expected number of queries required to traverse a uniformly random
search path in an arbitrary binary search tree built over the nonerased points in an α-erased n-element array
(Claim 3.2). This expectation depends only on the depth of the tree and α. This is the most interesting part
of our analysis and captures the intuition that a randomized binary search for a uniformly random search
point is biased towards visiting intervals containing a larger fraction of nonerased points.
BDPs on the hypergrid In Sections 4-5, we generalize our monotonicity tester in two ways: (1) to
work over general hypergrid domains, and (2) to apply to all BDPs. We achieve it by giving (1) a reduction
from testing BDPs on the line to testing monotonicity on the line that applies to erasure-resilient testers
and (2) an erasure-resilient version of the dimension reduction from [CDJS15].
Theorem 1.5 (BDP tester on the hypergrid). For every BDP P of real-valued functions on the hypergrid
[n]d , there exists a one-sided error
ε-tester that works for all α, ε ∈ (0, 1), where α ≤

 α-erasure-resilient
d log n
ε/970d, with query complexity O ε(1−α) .
Every known tester of a BDP for real-valued functions over hypergrid domains work by sampling an
axis-parallel line uniformly at random and checking for violations on the sampled line. Our erasure-resilient
testers also follow this paradigm. To check for violations on the sampled line, we use one iteration of our BDP
d
tester for the line. We show (in
√ Section 5.4) the existence of α-erased functions f : {0, 1} 7→ R that are ε-far
from monotone for α = Θ(ε/ d) but do not have violations to monotonicity along any of the axis parallel
lines (which are the edges of the hypercube, in this √
case). It implies that every tester for monotonicity that
follows the paradigm above will fail when α = Ω(ε/ d). Thus, some restriction on α in terms of d and ε is
necessary for such testers.
Convexity on the line Finally, in Section 6, we develop additional techniques to design a tester for
convexity (which is not a BDP) on the line. The query complexity of our tester has the same dependence
on n and ε as in the standard convexity tester of Parnas et al. [PRR03]. The dependence on n is optimal
for nonadaptive testers [BRY14], and the tester from [PRR03] is conjectured to be optimal in the standard
model.
Theorem 1.6 (Convexity tester on the line). There exists a one-sided error α-erasure-resilient ε-tester
for convexity
 of real-valued functions on the line [n] that works for all α, ε ∈ (0, 1), with query complexity
log n
.
O ε(1−α)
Our algorithm for testing convexity combines ideas on testing convexity from [PRR03], testing sortedness
from [EKK+00], and our idea of randomizing the search. The tester of [PRR03] traverses a uniformly random
path in a binary tree on the array [n] by selecting one of the half-intervals of an interval uniformly at random
5

at each step. Instead of doing this, our tester samples a uniformly random nonerased search point and
traverses the path to that point in a uniformly random binary search tree just as in our modification of the
tester of [EKK+ 00]. This is done to bias our algorithm to traverse paths containing intervals that have a
larger fraction of nonerased points. However, instead of checking whether the selected point can be found,
as in our monotonicity tester, the convexity tester checks a more complicated “goodness condition” in each
visited interval of the binary search tree. It boils down to checking that the slope of the functions between
pairs of carefully selected points satisfies the convexity condition. In addition to spending queries on erased
points due to sampling, like in the monotonicity tester, our tester also performs “walking queries” to find the
nearest nonerased points to the left and to the right of the pivots in our random binary search tree. We show
that the overhead in the query complexity due to querying erased points is at most a factor of O(1/(1 − α)).

2

Generic transformations

In this section, we explain our transformations that can make two classes of testers erasure-resilient: (1)
uniform proximity oblivious testers (POTs) defined by Goldreich and Ron [GR11] (Theorem 2.2), and (2)
uniform testers for extendable properties (Theorem 2.6).

2.1

Uniform POTs

POTs were studied by Goldreich and Ron in [GR11], Goldreich and Kaufman [GK11] and Goldreich and
Shinkar [GS16]. We first define POTs.
Definition 2.1 ([GS16]). Let P be a property, let ρ : (0, 1] 7→ (0, 1] be a monotone function and let c ∈ (0, 1]
be a constant. A tester T is a (ρ, c)-POT for P if
• for every function f ∈ P, the probability that T accepts is at least c, and
• for every function f ∈
/ P, the probability that T accepts is at most c − ρ(εf ), where εf denotes the
relative Hamming distance of f to P.
A POT that queries points sampled uniformly and independently at random from D is called a uniform
POT. Next, we state our first generic transformation.
Theorem 2.2. If T is a uniform (ρ,c)-POT for a property P that makes q queries, then there exists a
uniform α-erasure-resilient (ρ′ ,c)-POT T ′ for P that makes q queries for all α < ρ(εf · (1 − α))/q, where
ρ′ (x) = ρ(x · (1 − α)) − α · q for x ∈ (0, 1].
Proof. Let P be a property of functions over a domain D. The tester T ′ queries q uniform and independent
points from D. It accepts if the sample has an erased point. Otherwise, it runs T on the q sampled nonerased
points and accepts iff T accepts.
Consider an α-erased function f ∈ P and a restoration f r ∈ P. The tester T accepts f r with probability
at least c. If T accepts f r on querying a sample S ⊆ D, then T ′ also accepts f on S. Thus, the probability
that T ′ accepts f is at least c.
A tuple W ∈ Dq is a witness for a function g ∈
/ P, if T rejects upon sampling W . Consider an α-erased
function f that is ε-far from P. Every restoration f r of f is εf (1 − α)-far from P. Since T rejects f r with
probability at least 1 − c + ρ(εf (1 − α)), at least (1 − c + ρ(εf (1 − α))) · |D|q tuples in Dq are witnesses
for f r . Erasing one point can affect at most q · |D|q−1 witnesses. Thus, erasing an α fraction of points
can affect at most α · q · |D|q witnesses. At least (1 − c + ρ(εf (1 − α)) − α · q) · |D|q out of |D|q tuples are
witnesses with no points erased. The probability that T ′ samples such a tuple (and rejects f ) is at least
1 − c + ρ(εf (1 − α)) − α · q = 1 − c + ρ′ (εf ). Hence, the probability that T ′ accepts f is at most c − ρ′ (εf ).
This probability is nonnegative for all α < ρ(εf (1 − α))/q.

6

Low degree polynomials We apply Theorem 2.2 to a POT designed by Rubinfeld and Sudan [RS96]
for the property of being a polynomial of degree at most d over a finite field F and get an α-erasure-resilient
ε-tester for this property. Consider a function f : F 7→ F that we would like to test for being a polynomial of
degree at most d. The tester from [RS96] selects d + 2 points uniformly and independently at random from F
and checks whether there is a polynomial of degree at most d that fits all these points (by interpolation). It
accepts if there is such a polynomial and rejects otherwise. Call this tester T . The authors of [RS96] prove
that T rejects with probability at least ε if f is ε-far from being a degree-d polynomial. Therefore, T is a
(ρ, 1)-POT for this problem, where ρ is the identity function. By Theorem 2.2, there exists an α-erasureresilient (ρ′ , 1)-POT, say T ′ , that makes d + 2 queries, where ρ′ (x) = x(1 − α) − α · (d + 2). The probability
that T ′ rejects a function f that is ε-far from being a degree-d polynomial is at least ε(1 − α) − α · (d + 2).
The corollary follows.
Corollary 2.3. For α <

ε
,
d+2+ε


we can α-erasure-resilient ε-test for the property of being a degree-d poly
d+2
nomial over a field F using O ε(1−α)−α·(d+2)
uniform queries.

2.2

Uniform testers for extendable properties

We now define extendable properties and present our transformation for uniform testers for such properties.
Given S ⊆ T , the extension of a function f : S 7→ R to a domain T is a function g : T 7→ R that agrees
with f on every point in S.
Definition 2.4 (Extendable property).
For a domain D and all S ⊆ D, let PS denote a property of functions
S
over domain S. The property S⊆D PS is extendable if, for all S, T : S ⊆ T ⊆ D,
• for every function f ∈ PS , there is an extension f ′ ∈ PT , and

• for every function f that is ε-far from PS , every function f ′ ∈ PT differs from f on at least an ε
fraction of points in S.
The next lemma is used in the proof of our generic transformation.
S
Lemma 2.5. Let S⊆D PS be an extendable property. Consider an α-erased function f over domain D and
let N ⊆ D be the set of nonerased points in it. If f ∈ PD , then f|N ∈ PN . If f is ε-far from PD , then f|N
is ε-far from PN .
Proof. Suppose that f ∈ PD . Assume for the sake of contradiction that f|N ∈
/ PN . Therefore, no extension
of f|N to the domain D will satisfy PD . This contradicts our assumption that f ∈ PD . Now, suppose that
f is ε-far from PD . Then, every restoration of f needs to be changed in at least an ε fraction of nonerased
points to satisfy PD . Assume for the sake of contradiction that the relative Hamming distance of f|N to PN
is ε′ < ε. Let g be the function in PN closest to f|N . Let g e be an extension of g to D that satisfies PD .
Define an extension of f|N to D, say f e as follows. The function f e takes the same values as f|N on points
in N and takes the same values as g e on the remaining points. Note that f e is a restoration of f as well.
Clearly, f e can be made to satisfy PD by changing an ε′ < ε fraction of points on N , which contradicts the
assumption that f is ε-far from PD .
Our generic transformation for uniform testers for extendable properties follows.
Theorem 2.6. Let q(·, ·) be
S a function that is nondecreasing in the first argument and nonincreasing in
the second argument. LetS S⊆D PS be an extendable property. Suppose T is a uniform one-sided error
ε-tester for the property S⊆D PS , such that T makes q(|S|, ε) queries from S to test for PS , for every
S ⊆ D. Assume also that for every S ⊆ D, the probability that T tests PS correctly does not decrease when it
makes more queries. Then, there is a uniform one-sided error α-erasure-resilient ε-tester for PD that makes
O (q(|D|, ε)/(1 − α)) queries for all α ∈ [0, 1).

7

Proof. Let Q = 2q(|D|, ε)/(1−α). Consider the tester T ′ that samples Q points uniformly and independently
at random from D. If there are fewer than q(|D|, ε) nonerased points in the sample, T ′ accepts. Otherwise,
it runs T on the sampled nonerased points and accepts iff T accepts.
The expected number of nonerased points in a uniform sample of size Q from D is at least Q · (1 − α) =
2q(|D|, ε). By the Chernoff bound, the probability that T ′ samples fewer than q(|D|, ε) nonerased points is
at most e−q(|D|,ε)/4 .
Consider an α-erased function f over domain D. Let N be the set of nonerased points. If f ∈ P, then
f|N ∈ PN by Lemma 2.5, and the tester T ′ always accepts. Assume now that f is ε-far from P. Then
f|N is ε-far from PN by Lemma 2.5. Therefore T rejects with probability at least 2/3 on a sample of size
at least q(|N |, ε). Thus, by a union bound, the probability that T ′ accepts is at most 1/3 + e−q(|D|,ε)/4 .
This probability can be brought below 1/3 by repeating T ′ a small constant number of times, whenever
q(|D|, ε) ≥ 8.
In the following, we show a few applications of Theorem 2.2.
Convexity of Images A black and white image, represented by a function f : S 7→ {0, 1} for a subset
S of [n]2 , is convex if and only if for every pair of points u, v ∈ S such that f (u) = f (v) = 1, every point
t ∈ S on the line joining u and v satisfy f (t) = 1. Convexity is an extendable property. Testing whether an
image, represented by a function f : [n]2 7→ {0, 1}, is convex has been studied by Berman, Murzabulatov and
Raskhodnikova [BMR15]. The authors of [BMR15] give a one-sided error uniform ε-tester for this property
that makes O(1/ε4/3 ) uniform queries. Their proofs go through even if the domain of f is an arbitrary subset
of [n]2 . The corollary now follows by applying Theorem 2.6 to the tester in [BMR15].
Corollary
2.7.

 There is an α-erasure-resilient ε-tester for convexity of black and white images that makes
1
O (1−α)ε4/3 uniform queries, where ε ∈ (0, 1/2), α ∈ (0, 1).
Monotonicity over poset domains A real-valued function f defined on a partially ordered domain
is monotone if the function values respect the order relation
p of the poset. Monotonicity is an extendable
property. The tester by Fischer et al. [FLN+ 02] samples O( N/ε) points uniformly at random and checks
for violations to monotonicity among them. The corollary follows by applying Theorem 2.6 to this tester.
Corollary 2.8. There is an α-erasure-resilient
ε-tester for monotonicity of real-valued functions
q uniform


N
1
queries, where α ∈ (0, 1).
over N element posets that makes O (1−α) ·
ε
Boolean functions with k-runs A function f : [n] 7→ {0, 1} has k runs if the list f (1), f (2), . . . , f (n)
has at most k − 1 alternations of values. The problem is to test whether a given function f : [n] 7→ {0, 1}
has k runs or is ε-far from this property. Kearns and Ron [KR00] studied a relaxation of this problem.
Specifically, they showed that O(1/ε2 ) queries suffice to test whether a Boolean
function has k runs or
√
tester for this
is ε-far from being a k/ε-run function. They also developed a uniform O( k/ε2.5 )-query
√
relaxation and proved that every uniform ε-tester for the k-run property requires Ω( k) queries. Balcan
4
et al. [BBBY12] obtained
)-query tester for this property in the active testing model. They also
√ a O(1/ε
6
developed a uniform O( k/ε )-query tester4 . We show the following.
2
Theorem
oε > k /n, we can ε-test if a Boolean function over [n] has at most k runs using

n 2.9. √For
k
uniform and independent queries.
, ε6k
O min k·log
ε

Our tester for being a k-run function is given in Algorithm 1. It always accepts a function f that has at
most k runs. The following lemma implies Theorem 2.9.
Lemma 2.10. If f is ε-far from being a k-run function, Algorithm 1 rejects with probability at least 2/3.
4 Both [KR00] and [BBBY12] study Boolean functions over [0, 1]. We note that their algorithms will also work for Boolean
functions over [n].

8

Algorithm 1 Tester for k-run Boolean functions (ε,k,f : [n] 7→ {0, 1})
1:
2:

points uniformly and independently at random.
Query the values at 3(k+1)·log(k+1)
ε
Reject if the values of f at these points alternate k or more times with respect to the ordering on the
domain; accept otherwise.

Proof. For j ∈ [n] and b ∈ {0, 1}, let Tb,j denote the set consisting of the smallest ⌈n · ε/(k + 1)⌉ points in
the set {x : j ≤ x ≤ n and f (x) = b}, that is, the set of points between j and n where f takes the value b.
For a set S ⊆ [n], let max(S) denote the largest element in S. We will first describe a process to construct
a few disjoint subsets of [n] with some special properties.
• Let S1 = Tb,1 such that max(Tb,1 ) < max(T1−b,1 ).
• For i ≥ 2, the sets Si are defined as follows. Let the value that f takes on the elements in Si−1 be b
and let j = max(Si−1 ). Set Si = T1−b,j+1 . Stop if max(Si ) = n or Si = ∅.
The sets that this process constructs have the following properties. All Si ’s are subsets of [n]. Each point
in Si+1 is larger than every point in Si for all i. The function f takes the same value on all points in Si for
all i. The value of f on points in Si+1 is the complement of the value of f on points in Si for all i.
Next, we show that our process constructs sets S1 , S2 , . . . Sk+1 each of size ⌈n · ε/(k + 1)⌉, if f is ε-far
from satisfying the property. Let the process construct nonempty sets S1 , S2 , . . . St . Assume for the sake
of contradiction that t ≤ k. Let S1′ = {x : 1 ≤ x ≤ max(S1 )}. Let Si′ = {x : max(Si−1 ) < x ≤ max(Si )}
for all 1 < i ≤ t. Note that for all i ∈ [t], if f takes the value b on elements in Si , then f takes the value
1 − b on elements in Si′ \ Si . We will describe a function f ′ that has at most k runs. Set the values of f ′
on each x ∈ S1′ \ S1 to the value that f takes on S1 . For each 1 < i ≤ t, set the values of f ′ on Si to the
value of f on Si′ \ Si . On the rest of the points, f ′ takes the same value as f . We will now show that f ′ has
at most k alternating intervals. The function f ′ takes the same value on points in S1′ ∪ S2′ . Also, for each
′
1 < i ≤ t, the function f ′ is constant on Si′ . Thus, f ′ has at
√ most t runs. Also, f differs from f in at most
t · ⌈n · ε/(k + 1)⌉ ≤ k · ⌈n · ε/(k + 1)⌉ ≤ nε points, for k < nε. This is a contradiction.
Using the fact that k + 1 such subsets exist, we show that the tester will detect a violation with high
probability. For a particular i, the probability that none of the points selected by the algorithm lie in Si is
at most
3(k+1) log(k+1)/ε
(1 − ε/(k + 1))
≤ 1/(k + 1)3 .
Therefore, by a union bound, the probability that there exists an i such that none of the points selected by
the algorithm lies in Si is at most (k + 1)−2 < 1/3 for k ≥ 1.
Since the property of being a k-run function is extendable, applying Theorem 2.6 to Theorem 2.9 yields
the following corollary.
Corollary 2.11. For ε > k 2 /nand α ∈ (0,
n 1), we √canoα-erasure-resilient ε-test if a Boolean function over
k
1
uniform queries.
· min k·log
, ε6k
[n] has at most k runs using O 1−α
ε

3

Erasure-Resilient Monotonicity Tester for the Line

In this section, we prove Theorem 1.4. Recall that, for a function f : [n] 7→ R ∪ {⊥}, the set of nonerased
points (the ones that map to R) is denoted by N . The function f is monotone if x < y implies f (x) ≤ f (y)
for all x, y ∈ N . The tester does not know N in advance.
We present our tester in Algorithm 2. It has oracle access to f and takes α and ε as inputs. In each
iteration, it performs a randomized binary search for a nonerased index sampled uniformly at random (u.a.r.)
from N and rejects if it finds violations to monotonicity. In the description of our tester, we use I[i, j] to
denote the set of natural numbers from i until and including j. We alternatively refer to it as the interval
from i to j.
9

Algorithm 2 Erasure-Resilient Monotonicity Tester for the Line
m
l
60 log n
1: Set Q = ε(1−α) .
2: Accept at any point if the number of queries exceeds Q.
3: loop 2/ε times:
4:
Sample points uniformly at random from I[1, n] and query them until we get a point s ∈ N .
5:
Set ℓ ← 1, r ← n.
6:
while ℓ ≤ r do
7:
Sample points uniformly at random from I[ℓ, r] and query them until we get a point m ∈ N .
8:
if s < m then set r ← m − 1 and Reject if f (s) > f (m).
9:
if s > m then set ℓ ← m + 1 and Reject if f (s) < f (m).
10:
if s = m then Go to Step 3.
⊲ Search completed.
11: Accept.

Every iteration of Algorithm 2 can be viewed as a traversal of a uniformly random search path in a
uniformly random binary search tree defined on the set N of nonerased points. Given a binary search tree
T over N , we associate every node of T with a unique sub-interval I of I[1, n] as follows. The root of T is
associated with I[1, n]. Suppose the interval associated with a node Γ in T that contains s ∈ N is I[i, j].
Then the interval associated with the left child of Γ is I[i, s − 1] and the interval associated with the right
child of Γ is I[s + 1, j]. A search path is a path from the root to some node Γ of T .
If f is ε-far from monotone, we prove that, with high probability, the tester finds a violation. It is easy to
prove this, using a generalization of an argument from [EKK+ 00], for the case when Algorithm 2 manages
to complete all iterations of Step 3 before it runs out of queries. The challenge is that the algorithm might
get stuck pursuing long paths in a random search tree and waste many queries on erased points. To resolve
the issue of many possible queries to erased points, we prove an upper bound on the expected number of
queries made while traversing a uniformly random search path in a binary search tree on N . We combine
this with the fact that the expected depth of a random binary search tree is O(log n) to obtain the final
bound on the probability that the algorithm exceeds its query budget.

3.1

Analysis

We analyze the tester in this section. The query complexity of the tester is clear from its description. The
main statement of Theorem 1.4 follows from Lemma 3.1, proved next.
Lemma 3.1. Algorithm 2 accepts if f is monotone, and rejects with probability at least 2/3 if f is ε-far
from monotone.
Proof. The tester accepts whenever f is monotone. To prove the other part of the lemma, assume that f is
ε-far from monotone. Let A be the event that the tester accepts f . Let q denote the total number of queries
made. We prove that Pr[A] ≤ 1/3. The event A occurs if either q > Q or the tester does not find a violation
in any of the 2/ε iterations of Step 3. Thus, Pr [A] ≤ Pr [A|q ≤ Q] + Pr [q > Q] .
First we bound the probability that the tester does not find a violation in one iteration of Step 3,
conditioned on the event that q ≤ Q. Consider an arbitrary binary search tree T defined over points in N . A
point s ∈ N is called searchable with respect to T if Algorithm 2 does not detect a violation to monotonicity
while traversing the search path to s in T . Consider two indices i, j ∈ N , where i < j, both searchable with
respect to T . Let a ∈ N be the pivot corresponding to the lowest common ancestor of the leaves containing
i and j. Since i and j are both searchable, it must be the case that f (i) < f (a) and f (a) < f (j) and hence,
f (i) < f (j). Thus, for every tree T , the function restricted to the domain points that are searchable with
respect to T is monotone. Therefore, if f is ε-far from monotone, for every binary search tree T , at least an
ε-fraction of the points in N are not searchable. Thus, the tester detects a violation with probability ε in
2
each iteration. Consequently, Pr [A|q ≤ Q] ≤ (1 − ε) ε < 1/4.
10

In the rest of the proof, we bound Pr[q > Q]. We state and prove a claim that bounds the expected
number of queries to traverse a search path, for every binary search tree. Recall that a search path in a
search tree T is a path from the root to some node in T . Let I be an interval associated with a node v
of T and let αI denote the fraction of erased points in I. The number of queries to be made to sample a
nonerased point from I with uniform sampling is a geometric random variable with expectation 1/(1 − αI ).
We define the query-weight of node v to be this expectation. The query-weight of a search path is the sum of
query-weights of the nodes on the path (which is the expected number of queries that the algorithm makes
while traversing that path).
Claim 3.2. Consider an arbitrary binary search tree T on N of height h. The expected query-weight of a
uniformly random search path in T is at most h/(1 − α).
Proof. There are exactly |N | search paths in T . Let S denote the sum of query-weights of all the search
paths. The expected query-weight is equal to S/|N |.
Consider a node v in T associated with an interval I. There are |I|(1 − αI ) nonerased points in I. The
search paths from the root of T to all these nonerased points pass through v, and hence, the query-weight
of v gets added to the query-weights of all of those paths. Therefore, the total contribution of v towards S
is |I|, since the query-weight of v is 1/(1 − αI ). Note that the intervals associated with nodes at the same
level of T are disjoint from each other. Therefore, the total contribution to S from all nodes on the same
level of T is at most n. Hence the value of S is at most n · h. Observe that this quantity is independent of
the fraction of erasures α. Therefore, the expected query-weight of a search path is at most n · h/|N |, which
is at most h/(1 − α), since |N | ≥ n · (1 − α).
We will next see a fact on the expected depth of a uniformly random binary search tree and combine it with
the above claim to prove the required bound on the expected query-weight of a uniformly random search
path in a uniformly random binary search tree.
Claim 3.3 ([Ree03]). If Hn is the random variable denoting the height of a random binary search tree on n
nodes, then E[Hn ] ≤ 5 log n.
Corollary 3.4. The expected number of queries made by Algorithm 2 to traverse a uniformly random search
path in a uniformly random binary search tree on N is at most 5 log n/(1 − α).
By linearity of expectation, the expected number of queries made by the tester over all its iterations is
at most 10 log n/(ε · (1 − α)). Applying Markov’s inequality to q, we can then see that Pr[q > Q] ≤ 1/6.
Therefore, the probability of the tester not finding a violation is at most 1/3. This completes the proof of
the lemma.

4

Erasure-Resilient Monotonicity Testers for the Hypergrid

In this section, we present our erasure-resilient tester for monotonicity over hypergrid domains and prove
the following theorem, which is a special case of Theorem 1.5. We present the erasure-resilient testers for
general BDPs in Section 5.
Theorem 4.1. There exists a one-sided error α-erasure-resilient ε-tester for monotonicity of real-valued
functions on the hypergrid [n]d that works for all α, ε ∈ (0, 1), where α ≤ ε/250d, with query complexity
d log n
).
O( ε(1−α)
Let L denote the set of all axis-parallel lines in the hypergrid. Our monotonicity tester, which is described
in Algorithm 3, samples an axis-parallel line uniformly at random in each iteration and does a randomized
binary search for a uniformly randomly sampled nonerased point on that line. It rejects if and only if
a violation to monotonicity is found within its query budget. To analyze the tester, we first state two
important properties of a uniformly random axis-parallel line in Lemma 4.2 and Lemma 4.3, which we jointly
call the erasure-resilient dimension reduction. The statements and proofs of more general versions of these
lemmas, applicable to all BDPs, are given in Section 5.
11

Lemma 4.2 (Dimension reduction: distance). Let εf be the relative Hamming distance of an α-erased
function f : [n]d 7→ R ∪ {⊥} from monotonicity. Given an axis-parallel line ℓ ∈ L, let fℓ : [n] 7→ R ∪ {⊥}
denote the restriction of f to ℓ and let εℓ denote the relative Hamming distance of fℓ from monotonicity.
Then Eℓ∼L [εℓ ] ≥ (((1 − α) · εf )/4d) − α.
Lemma 4.3 (Dimension reduction: fraction of erasures). Consider an α-erased function f : [n]d 7→ R ∪ {⊥}.
Given ℓ ∈ L, let αℓ denote the fraction of erased points in ℓ. Then, for every η ∈ (0, 1), we have, Prℓ∼L [αℓ >
α/η] ≤ η.
Algorithm 3 Erasure-Resilient Monotonicity Tester for [n]d
d

Require: parameters ε ∈ (0, 1), α ∈ [0, ε/250d]; oracle access to f : [n] → R
1200d·log n
1: Set Q = ⌈ ε(1−α) ⌉.
2:

3:
4:
5:
6:
7:

12d
times:
loop ε(1−α)−4dα
Sample a line ℓ ∈ L uniformly at random.
Sample and query points u.a.r. from ℓ and query them until we get a point s ∈ N .
Perform a randomized binary search for s on ℓ as in Algorithm 2.
Reject if any violation to monotonicity is found.
Accept at any point if the number of queries exceed Q.

The query complexity of the tester is evident from its description. We will now prove its correctness in
the following lemma, which will then imply Theorem 4.1.
Lemma 4.4. Algorithm 3 accepts if f is monotone, and rejects with probability at least 2/3 if f is ε-far
from monotone.
Proof. The tester accepts if f is monotone. So, assume that f is ε-far from being monotone. Let A denote
the event that the tester does not find a violation to monotonicity in any of its iterations. If q denotes the
total number of queries made by the tester, we have, Pr[A] ≤ Pr[A|q ≤ Q] + Pr[q > Q].
Let t denote the number of iterations of the tester. Let Ai denote the event that the tester does not find
a violation in its i-th iteration. For ℓ ∈ L, let fℓ denote f restricted to the
P line ℓ. Let εℓ denote the relative
Hamming distance of fℓ from monotonicity. We have, Pr[Ai |q ≤ Q] = ℓ∈L (1 − εℓ ) Pr[ℓ] = 1 − Eℓ∼L [εℓ ].
(1−α)·εf
By Lemma 4.2 and the fact that εf ≥ ε, we have, Eℓ∼L [εℓ ] ≥
− α ≥ (1−α)·ε
− α. Therefore,
4d
4d
t
Y


t
(1 − α) · ε − 4dα
1
Pr[Ai |q ≤ Q] ≤ 1 −
Pr[A|q ≤ Q] =
<
.
4d
10
i=1
It now remains to bound Pr[q > Q]. Let η stand for 1/10t. Let αi denote the fraction of erasures in
the line sampled during iteration i and let qi denote the number of queries made by the algorithm during
iteration i. Let G denote the (good) event that αi ≤ α/η for all iterations i ∈ [t]. By Corollary 3.4, E[qi |G] ≤
5η · log n/(η − α), and by the linearity of expectation, E[q|G] ≤ log n/(2(η − α)) ≤ 120d log n/(ε(1 − α)),
where the last inequality follows from our assumption that α ≤ ε/250d. Using Markov’s inequality, Pr[q >
Q|G] ≤ 1/10. Also, by combining Lemma 4.3 with a union bound, we can see that Pr[G] ≤ 1/10. Therefore,
Pr[q > Q] ≤ Pr[q > Q|G] + Pr[G] ≤ 1/5.

5

Erasure-Resilient BDP Testing

In this section, we discuss our erasure-resilient testers for all bounded derivative properties over hypergrid
domains and prove Theorem 1.5. First, we show in Lemma 5.4 that testing for any BDP on [n] reduces
to testing monotonicity on [n]. Next, we prove Lemma 5.7 and Lemma 5.8 that reduces the problem of
erasure-resilient testing of a BDP over hypergrid domains to testing of the same property over the line.
12

5.1

Erasure-Resilient BDP Tester for the Line

In Lemma 5.4, we show that (erasure-resilient) testing of bounded derivative properties (BDPs) on the line
reduces to monotonicity testing on the line and prove Theorem 5.5. As noted in Section 1.2, BDPs comprise
of a large class of properties that have been studied in the property testing literature.
Given a function f : [n] 7→ R ∪ {⊥}, and a bounded derivative property P, we first define the notion of a
violated pair in f with respect to P.
Definition 5.1 (Violated pair). Given a function f : [n] 7→ R ∪ {⊥} and bounding family B consisting of
functions l, u : [n − 1] 7→ R, two points x, y ∈ N such that x < y violate the property P(B) with respect to f
Py−1
Py−1
if f (x) − f (y) > mB (x, y) = − t=x
l(t) or f (y) − f (x) > mB (y, x) = t=x
u(t). The pairs (x, y) and (y, x)
are called violated.
Consider a bounded derivative property P of functions defined over [n] and associated bounding functions
l, u : [n − 1] 7→ R. The following claim states that, we may assume w.l.o.g. that l(i) = −u(i) for all i ∈ [n−1].
We use it in the proof of Claim 5.3.
Claim 5.2. Consider a function f : [n] → R ∪ {⊥} and a bounding function family B over [n] with
Pn−1
l, u : [n − 1] 7→ R. Let g : [n] 7→ R ∪ {⊥} be a function that takes the value f (i) + j=i l(j)+u(j)
for
2
each i ∈ N and is erased on the remaining points. Let B′ be a bounding function family over [n] with
l′ , u′ : [n − 1] 7→ R such that u′ (i) = −l′ (i) = u(i)−l(i)
for all i ∈ [n − 1]. Then x, y ∈ N violate P(B) with
2
respect to f iff x, y violate P(B′ ) with respect to g.
Proof. Note that (x, y) ∈ N , where x < y, is not violated with respect to f if and only if max{f (x) − f (y) −
mB (x, y), f (y) − f (x) − mB (y, x)} ≤ 0. We have
g(x) − g(y) − m (x, y) = f (x) − f (y) +
B′

= f (x) − f (y) −

y−1
X
u(i) + l(i)

i=x
y−1
X
i=x

2

−

y−1
X
u(i) − l(i)
i=x

2

l(i) = f (x) − f (y) − mB (x, y).

Also,
g(y) − g(x) − mB′ (y, x) = f (y) − f (x) −
= f (y) − f (x) −

y−1
X

i=x
y−1
X
i=x

y−1

u(i) + l(i) X u(i) − l(i)
−
2
2
i=x
u(i) = f (y) − f (x) − mB (y, x).

Thus, max{g(x) − g(y) − mB′ (x, y), g(y) − g(x) − mB′ (y, x)} = max{f (x) − f (y) − mB (x, y), f (y) − f (x) −
mB (y, x)}. The claim follows.
The following claim shows a reduction from testing BDPs over [n] to testing monotonicity over [n].
Claim 5.3. Consider an α-erased function f : [n] 7→ R ∪ {⊥} and bounding functions l, u : [n − 1] 7→ R such
that −l(i) = u(i) = γ(i) for all i ∈ [n − 1]. Let P be the BDP defined by l and u. Let g, h : [n] 7→ R ∪ {⊥}
Pn−1
Pn−1
be two functions that take the values g(i) = f (i) − r=i γ(r) and h(i) = −f (i) − r=i γ(r) for all i ∈ N
and are erased on the remaining points. Then, the following conditions hold:
1. x, y ∈ N violate P with respect to f iff x, y violate monotonicity with respect to either g or h.
2. If f is in P, then both g and h are both monotone.
3. If f is ε-far from P, then either g or h is at least ε/4-far from monotonicity.
13

Proof. Consider a pair (i, j) ∈ N × N where i < j. We have,
g(i) − g(j) = f (i) − f (j) −

j−1
X

γ(r)

and

r=i

h(i) − h(j) = f (j) − f (i) −

j−1
X

γ(r).

r=i

P
Pj−1
If (i, j) is not violated with respect to f , we have f (j)−f (i)− j−1
r=i γ(r) ≤ 0 and f (i)−f (j)−
r=i γ(r) ≤
0. Thus, (i, j) satisfies the monotonicity property with respect to g and h. If (i, j) is violated with respect
P
Pj−1
to f , then either f (j) − f (i) − j−1
r=i γ(r) > 0 or f (i) − f (j) −
r=i γ(r) > 0. That is, either g or h violates
monotonicity.
Define the violation graph Gf as follows. The vertex set corresponds to N . There is an (undirected)
edge between i ∈ N and j ∈ N iff the pair (i, j) violates the property P. By Lemma 2.5 in [CDJS15], the
size of every maximal matching is at least ε · |N |/2. Consider a maximal matching M in Gf . From the
discussion above, every edge in M violates monotonicity with respect to either g or h. Therefore, at least
ε · |N |/4 edges are violated with respect to at least one of g and h. Assume w.l.o.g. that at least ε · |N |/4
edges from M are violated with respect to h. One has to change the function value of at least one endpoint
of each edge to repair it. Since M is a matching in the violation graph Gh as well, at least ε · |N |/4 function
values of h have to change to make h monotone. This means that h is at least ε/4-far from monotone.
Therefore, in order to test the bounded derivative property P on f with proximity parameter ε, one can
test monotonicity on g and h with proximity parameter ε/4 and error probability 1/6 and accept iff both
tests accept.
Lemma 5.4. Let Qmon (α, ε, n) denote the query complexity of α-erasure-resilient ε-testing of monotonicity of
real-valued functions on the line. Then, for every BDP, α-erasure-resilient ε-testing of real-valued functions
on the line has query complexity O(Qmon (α, ε/4, n)). The same statement holds for 1-sided error testing.
The following theorem is a direct consequence of Lemma 5.4 and Theorem 1.4.
Theorem 5.5 (BDP tester on the line). For every BDP P, there exists a one-sided error α-erasure-resilient
ε-tester
for P of real-valued functions on the line that works for all α, ε ∈ (0, 1), with query complexity

1
O 1−α · logε n .

5.2

Erasure-Resilient Dimension Reduction

In this section, we prove two important properties of a uniformly random axis parallel line in the hypergrid
[n]d . We do this in Lemma 5.7 and Lemma 5.8, which we jointly call erasure-resilient dimension reduction.
We first introduce some notation.
Let g be an α-erased function on D, and N ⊆ D be the set of nonerased points in g. The Hamming
distance of g from P, denoted by dist(g, P), is the least number of nonerased points on which every restoration
of g needs to be changed to satisfy P. The relative Hamming distance between g and P is dist(g, P)/|N |.
We use g|S to denote the restriction of g to a subset S ⊆ D. Note that all these definitions make sense even
for functions with no erasures in them.
Let P be a bounded derivative property of functions defined over [n]d . Let L denote the set of all axisparallel lines in [n]d . Let P i denote the set of functions over D with no violations to P along dimension i
for all i ∈ [d]. Consider an α-erased function f : [n]d 7→ R ∪ {⊥}. Let N ⊆ [n]d denote the set of nonerased
points in f . Let ℓ ∈ L be an axis-parallel line. Let Nℓ denote the set of nonerased points on ℓ and fℓ denote
the function f restricted to ℓ.
Lemma 5.7 shows that the expected relative Hamming distance of fℓ from P is roughly proportional to
the relative Hamming distance of f from P. First, we prove Claim 5.6 that we use in our proof of Lemma 5.7.
Claim 5.6.

d

X
1
dist(f, P i ) + α · d · nd .
dist(f, P) ≤
4
i=1
14

Proof. Let g : [n]d 7→ R be a function in P such that dist(g|N , f|N ) is minimum. We define f∗ : [n]d 7→ R, a
restoration of f , such that f∗ (x) = f (x) for all x ∈ N and f∗ (x) = g(x) for all x ∈
/ N . Note that g is the
function closest to f∗ in P.
i
Also, for all i ∈ [d], let f∗i : [n]d 7→ R in P i be such that dist(f∗|N
, f|N ) is minimum. Therefore, we have,
1
1
dist(f, P) ≤ dist(f∗ , P)
4
4
d
X
dist(f∗ , P i )
≤

by dimension reduction from [CDJS15]

i=1

≤

d
X

dist(f∗ , f∗i )

≤

d
X

dist(f, P i ) + d · α · nd .

i=1

i=1

because f∗i ∈ P i

The last inequality holds because, by triangle inequality, for all i ∈ [d],
dist(f∗ , f∗i ) ≤ dist(f, P i ) + α · nd .
We now use Claim 5.6 to prove the first part of our dimension reduction.
Lemma 5.7 (Dimension reduction: distance). Let εf be the relative Hamming distance of f from P. Given
ℓ ∈ L, let εℓ denote the relative Hamming distance of fℓ from P. Then
Eℓ∼L [εℓ ] ≥

(1 − α) · εf
− α.
4d

Proof. There are d axis-parallel directions and, therefore, dnd−1 axis-parallel lines in [n]d . Thus, the probability of picking a specific axis parallel line ℓ uniformly at random is 1/dnd−1 . Let Li denote the set of axis
parallel lines along dimension i.
X
Eℓ∼L [εℓ ] =
εℓ · Pr(ℓ)
ℓ∈L

=

d X
X

i=1 ℓ∈Li

=

εℓ · Pr(ℓ)

d X
X
1
dist(fℓ , P)
·
dnd−1 i=1
|Nℓ |
ℓ∈Li

≥

d X
X

1
·
dnd i=1

ℓ∈Li

dist(fℓ , P)

d
1 X
·
dist(f, P i )
dnd i=1


1
dist(f, P)
d
·
− αd · n
≥
dnd
4
1−α
≥
· εf − α.
4d

since |Nℓ | ≤ n

=

15

by Claim 5.6

We conclude this section with the second part of our dimension reduction.
Lemma 5.8 (Dimension reduction: fraction of erasures). Consider an α-erased function f : [n]d 7→ R ∪ {⊥}.
Given an axis-parallel line ℓ ∈ L, let αℓ denote the fraction of erased points in ℓ. Then, for every η ∈ (0, 1),
Pr [αℓ > α/η] ≤ η.

ℓ∼L

Proof. Note that a uniformly randomly sampled point in [n]d is erased with probability α. We can sample
a point uniformly at random by first sampling a line ℓ ∈ L uniformly at random and then sampling a point
uniformly randomly on ℓ, which is erased with probability αℓ . Therefore we have
X
α=
Pr[ℓ] · αℓ = Eℓ∼L [αℓ ].
ℓ∈L

The claim then follows from Markov’s inequality.

5.3

Erasure-Resilient BDP Testers for the Hypergrids

We now present our erasure-resilient tester for an arbitrary BDP P and complete the proof of Theorem 1.5.
Let B = {ℓi , ui : i ∈ [d]} be a bounding family for P and let Li denote the set of axis-parallel lines
along dimension i. Our tester is given in Algorithm 4. The analysis of this tester is very similar to that
of Algorithm 3 and is omitted.
Algorithm 4 Erasure-Resilient BDP Tester for [n]d
d
Require: parameters
ε ∈ (0,

 1), α ∈ [0, ε/970d]; oracle access to f : [n] → R
4800d · log n
1: Set Q =
.
ε(1 − α)
48d
2: loop
times:
ε(1 − α) − 4dα

3:
4:
5:
6:
7:
8:

Sample a line ℓ ∈ L uniformly at random.
Define g and h from fℓ , ℓi and ui as in Claim 5.3 if ℓ is sampled from Li .
Sample points u.a.r. from ℓ and query them until we get a point s ∈ N .
Perform a randomized binary search for s on ℓ as in Algorithm 2.
Reject if any violation to monotonicity is found in either g or h.
Accept at any point if the number of queries exceed Q.

5.4

Limitations of Dimension Reduction based Erasure-Resilient Testers

In this section, we show that when the fraction of erasures is large enough, dimension reduction based testers
that sample axis parallel lines uniformly at random and check for violations on them, are bound to fail. More
precisely we prove the following claim.
d
Lemma
√ 5.9. For all ε ∈ (0, 1/2], there exists an α-erased function f : {0, 1} 7→ R ∪ {⊥}, where α =
Θ(ε/ d), such that for large enough d, the function f is ε-far from monotone and no axis-parallel edge in
{0, 1}d is violated in f .

Proof. For the ease of exposition, we prove this lemma for ε = 1/2. We note that similar calculations could
extend this proof to any ε ∈ (0, 1/2]. For x ∈ {0, 1}d, the function f is defined as:

 ⊥ if ||x||0 = d/2
1
if ||x||0 < d/2
f (x) =

0
otherwise.
16

Note that the function f , when restricted to N , is 1/2-far from being monotone. Also, no axis-parallel
edge is violated
with respect to monotonicity. This completes the proof for the case when ε = 1/2, since
√
α = Θ(1/ d).
For general ε, we can define the set of erased points to be the points in {0, 1}d, such that their Hamming
weight is β · d, where β = β(ε) < 1/2 is chosen so that |S|/2d = ε, where S is the set of all points in {0, 1}d
with Hamming weight less than β · d. As in the above case, we set all points with Hamming weight smaller
than β · d to 1 and the ones with Hamming weight larger than√β · d to be 0. Similar calculations help us
prove that for large enough d, fraction of erased points is Θ(ε/ d). In this case, f is ε-far from monotone,
but no axis-parallel edge is violated in f with respect to monotonicity.

6

Erasure-Resilient Convexity Tester for the Line

In this section, we prove Theorem 1.6. Given an α-erased function f : [n] 7→ R ∪ {⊥}, let νi denote the i-th
)−f (νi )
nonerased domain point in [n]. The derivative of f at a point νi ∈ N , denoted by ∆f (νi ), is f (ννi+1
,
i+1 −νi
whenever νi+1 ≤ n. The function f is convex iff ∆f (νi ) ≤ ∆f (νi+1 ) for all i ∈ [|N | − 2]. Our tester builds
upon the ideas in the convexity tester from [PRR03].
A high level idea of the tester is as follows. Our tester (Algorithm 5) has several iterations. Every
iteration of the tester can be thought of as a traversal of a uniformly random search path of a uniformly
random binary search tree on N , just as Algorithm 2. For each interval on such a path, we check a set of
conditions computed based on the values at some nonerased points in the interval, called anchor points, and
two real numbers, called the left and right slopes. More specifically, we verify that the function restricted to
the sampled nonerased points in the interval is convex, by comparing the slopes across consecutive points.
The algorithm accepts if all the intervals it sees pass these checks. The main steps in the analysis of the
Algorithm 5 Erasure-Resilient Convexity Tester
Require: parameters ε, α ∈ (0, 1); oracle access to f : [n] 7→ R ∪ {⊥}.
180 log n
1: Set Q = ⌈ ε(1−α) ⌉.
2: Accept at any point if the number of queries exceeds Q.
3: loop 2/ε times
4:
Sample points in I[1, n] u.a.r and query them until we get a point s ∈ N .
5:
Test-Interval(I[1, n], ∅, −∞, +∞, s) and Reject if it rejects.
6: Accept.
tester follows that of the analysis of Algorithm 2. To analyze the tester, we first prove that, with high
probability, the algorithm does not run out of its budget of queries Q. For this, we classify the queries
that the tester makes into two kinds and analyze them separately. The queries where the tester repeatedly
samples and queries from an interval until it finds a nonerased domain point are called sampling queries.
The queries where the tester keeps querying consecutive points, starting from a nonerased point, until it gets
the next nonerased point are called walking queries. In the proof of Lemma 6.1, we show that the expected
number of walking queries is at most twice the number of the expected number of the sampling queries and
use Corollary 3.4 to bound the expected number of sampling queries. In the second part of the analysis we
prove that, conditioned on the aforementioned event happening, in every iteration, with probability at least
ε, the tester will detect a violation while testing on a function that is ε-far from being convex. This part
draws ideas from the proof of correctness of the tester in [PRR03].
Lemma 6.1. Algorithm 5 accepts if f is convex, and rejects with probability at least 2/3 if f is ε-far from
convex.
Proof The tester accepts whenever f is convex. To prove the other part of the lemma, assume that f is
ε-far from being convex. Let A be the event that the tester accepts f . Let q denote the total number of
queries made. We have, Pr [A] ≤ Pr [A|q ≤ Q] + Pr [q > Q] .
17

Procedure 6 Test-Interval(I[i, j], A = {a1 , a2 , . . . , ak }, mℓ , mr , s)
Require: interval I[i, j]; a set of nonerased points A; left slope mℓ ∈ R; right slope mr ∈ R; search point
s ∈ N.
1: Sample points u.a.r. from I[i, j] and query them until we get a point x ∈ N .
2: Sequentially query points x + 1, x + 2 . . . until we get a nonerased point y.
3: Sequentially query points x − 1, x − 2 . . . until we get the nonerased point z.
4: Let (a1 , a2 , . . . , ak ) denote the sorted list of points in the set A ∪ {x, y, z}.
5: Let mi = (f (ai+1 ) − f (ai ))/(ai+1 − ai ) for all i ∈ [k − 1].
6: Reject if mℓ ≤ m1 ≤ m2 ≤ · · · ≤ mk−1 ≤ mr is not true.
7: Let A′ℓ and A′r be the sets of points in A that are smaller and larger than x, respectively.
8: if s < x then
9:
Reject if Test-Interval(I[i, z], A′ℓ , mℓ , ∆f (z), s) rejects.
10: if s > x then
11:
Reject if Test-Interval(I[y, j], A′r , ∆f (x), mr , s) rejects.
12: Accept.

By Corollary 3.4, the expected number of sampling queries made in one iteration of the tester is at most
5 log n/(1 − α).
We will now bound the expected number of walking queries. Consider an interval I with αI fraction of
erasures in it. A point in I can get queried as part of the walking queries if either the first nonerased point to
its right or the first nonerased point to its left on the line [n] gets sampled as the pivot of I. For a nonerased
point i ∈ I,Plet w(i) denote the number of walking queries to be made if the algorithm samples i as the pivot.
Therefore i∈N ∩I w(i) ≤ 2|I|, since every point in I gets counted at most twice in this sum. There are at
least |I|(1 − αI ) non erased points in I and each of them could be the pivot in I with equal probability.
Hence, the expected number of walking queries that Algorithm 5 makes in I is at most 2/(1 − αI ). This is
at most twice the expected number of sampling queries that the algorithm makes in I.
Therefore, by the linearity of expectation, the expected number of walking queries made in one iteration
of the tester is at most 10 log n/(1 − α). Thus, the expected value of the total number of queries made by
the tester in one iteration is at most 15 log n/(1 − α) and that over all iterations is at most 30 log n/ε(1 − α).
Thus, by Markov’s inequality, Pr[q > Q] ≤ 1/6.
Next, we bound Pr[A|q ≤ Q]. We first define some notation for that. Consider a search path traversed by
the algorithm. Let I[i, j] be an interval on the path. Consider the execution of Test-Interval (Procedure 6)
called with I[i, j] as the first argument. We call the nonerased point x sampled in Step 1 its pivot, the set of
points A′ in Step 4 its anchor set and the values mℓ and mr as its left and right slopes, respectively. That
is, given a binary search tree T , we associate each interval appearing in the tree with a pivot, an anchor set
and two slopes.
Consider a binary search tree T and a function f : [n] 7→ R ∪ {⊥}. Let I[i, j] be an interval appearing
in T with anchor set A = {a1 , a2 , . . . , ak } and slopes mℓ and mr such that ai ≤ ai+1 for all i ∈ [k − 1]. Let
mi = (f (ai+1 ) − f (ai ))/(ai+1 − ai ) ∀i ∈ [k − 1].
Definition 6.2 (Good Interval, Bad Interval). An interval I[i, j] is good if mℓ ≤ m1 ≤ m2 ≤ · · · ≤ mk−1 ≤
mr . Otherwise, it is bad.
Definition 6.3 (Violator Interval). An interval I[i, j] is a violator if it is bad and all its ancestor intervals
in T are good.
Definition 6.4 (Witness). A nonerased domain point is a witness with respect to T if it belongs to a violator
interval in T .
We prove that if f is ε-far from being convex, then, for every binary search tree T , the fraction of
nonerased domain points that are witnesses is at least ε. We start by assuming that there is a tree in which

18

the fraction of witnesses is less than ε. We show that we can correct the function values only on the witnesses
and get a convex function, which gives a contradiction.
Claim 6.5. If f is ε-far from convex, then the fraction of witnesses in every binary search tree T is more
than ε.
Proof. Assume for the sake of contradiction that there is a binary search tree T such that the fraction of
witnesses with respect to T is at most ε. In the following, we will construct a convex function g : [n] 7→ R∪{⊥}
by changing the values of f only on witnesses with respect to T . Since the fraction of witnesses is at most
ε, functions f and g will differ on at most an ε fraction of nonerased domain points, which results in a
contradiction.
Consider a violator interval I[i, j] in T . Since, by our assumption, the fraction of witnesses is at most ε,
the interval I[i, j] cannot be the whole interval for otherwise, we have a contradiction immediately. Let the
anchor set and slopes associated with the parent interval of I[i, j] be A = {a1 , a2 , . . . , ak } and mℓ and mr ,
respectively such that ai ≤ ai+1 for all i ∈ [k − 1]. Assume that I[i, j] is the right child of its parent. The
case when I[i, j] is the left child of its parent is similar. Let {au , au+1 , . . . , ak } be the set of points common
to I[i, j] and A. By definition, au is the smallest nonerased domain point in I[i, j]. Also, the left slope of
I[i, j] is (f (au ) − f (au−1 ))/(au − au−1 ) and its right slope is equal to mr .
Let mv = (f (av+1 ) − f (av ))/(av+1 − av ) for all integers v such that v ∈ [u − 1, k). We define g as follows.
• For each t ∈ {au , au+1 , . . . , ak }, set g(t) = f (t) .
• For each integer v ∈ [u, k) and t ∈ N ∩ (av , av+1 ), set
g(t) = f (av ) + mv · (t − av )
• For each t ∈ N such that t > ak , set
g(t) = f (ak ) + mk−1 · (t − ak ).
Since I[i, j] is a violator, the parent interval of I[i, j] is good, by definition. This implies that mu−1 ≤ mu ≤
. . . ≤ mk ≤ mr . Therefore, the derivatives of nonerased points in I[i, j] are non-decreasing with respect to
g, by virtue of our assignment.
To prove that g is convex, we first show that every interval in T is good with respect to g.
1. Consider an interval I in T that is good with respect to f . If I has no ancestors or descendants that
are violators, it remains good with respect to g as well, since g(t) = f (t) for all t ∈ I[i, j].
2. Consider an interval I that has a descendant I ′ that is a violator. The definition of g on points in
I ′ ensures that g(t) = f (t) for every point t common to the anchor sequence of I and the interval I ′ .
Thus, I remains good with respect to g.
3. Consider a node I that is either a violator or has a violator ancestor I ′ . By definition, the parent of
I ′ is good with respect to f . Therefore, by the definition of g on I ′ , we have ∆g(t − 1) ≤ ∆g(t) for all
t ∈ N such that t ∈ I ′ . Therefore, I ′ is good with respect to g, and hence I is also good with respect
to g.
We proved that every interval in the tree T is good with respect to g. We now prove that g is convex.
Consider a point νt ∈ N such that 2 ≤ t ≤ |N | − 1.
This point occurs in T either as a pivot in a non-leaf interval or as the sole nonerased domain point in a
leaf interval. In the former case, the condition ∆f (νt−1 ) ≤ ∆f (νt ) is part of the goodness condition of the
corresponding interval and is satisfied. In the latter case, ∆f (νt−1 ) and ∆f (νt ) are the left and right slopes
of the leaf and are compared as part of the goodness condition of the leaf. Thus, ∆f (νt−1 ) ≤ ∆f (νt ) for all
νt ∈ N such that 2 ≤ t ≤ |N | − 1. Thus, g is convex.
19

We conclude our analysis by bounding the probability that the tester does not find a violation. Since the
search point s is chosen uniformly at random from the set of nonerased domain points, the probability that
it is a witness is at least ε and thus, the tester detects a violation to convexity with probability at least ε in
2
every iteration. Therefore, Pr[A|q ≤ Q] is at most (1 − ε) ε < 1/6.

7

Relations to Other Testing Models

In this section, we describe the relationships between erasure-resilient testing model and the other models
of property testing. We first describe a property that is easy to test in the standard model, but is hard
to test in the erasure-resilient model. This effectively separates the erasure-resilient testing model from the
standard model. We discuss this result in Section 7.1. Next, we study the connection of erasure-resilient
testing to that of distance approximation algorithms and show that the existence of distance approximation
algorithms for a property implies erasure-resilient testing algorithms for the same property. We describe it
in Section 7.2.

7.1

Separation Between Erasure-Resilient and Standard Testing

In this section we prove the following theorem that shows a separation between erasure-resilient testing and
standard testing.
Theorem 7.1. There exists a property R such that R can be ε-tested in the standard model using O(1/ε)
queries. However, there exists some c > 0 such that for all α = Ω( log logn log n ) and ε ∈ (0, 1), every α-erasureresilient ε-tester for R has to make at least nc queries.
The property R in Theorem 7.1 is the property that was proposed by Fischer and Fortnow [FF06] to
separate tolerant testing [PRR03] from standard testing. The first part of the theorem is already proved in
their paper. Our proof for the other part closely follows the proof in [FF06] that separates tolerant testing
and standard testing. We first recall some definitions from [FF06].
Definition 7.2 (PCP witness [FF06]). Given a promise problem and a Boolean input v1 , . . . , vn , a (onesided) PCP witness for the problem is a set of Boolean functions f1 , . . . , fl , where l is polynomial in n,
satisfying the following:
• The number of variables each of the functions depend on is independent of n. These variables might
include variables from v1 , . . . , vn as well as from a set of additional variables w1 , . . . , wm such that m
is polynomial in n.
• If the input is a Yes instance of the promise problem, then there is an assignment to w’s such that all
fi ’s are satisfied.
• If the input is a No instance of the promise problem, then for all assignments of values to w’s, at most
half of the functions are satisfied.
Definition 7.3 (PCP of proximity [BGH+ 06, FF06]). A PCP of proximity is a PCP witness for an ε-testing
promise problem.
The following lemma talks about the existence of PCPs of proximity for properties having polynomialsized circuits.
Lemma 7.4 ([BGH+ 06]). If P is a property of v1 . . . , vn that is decidable by a circuit of size k, and
t < log log k/ log log log k, then there exists a PCP of proximity for P with distance parameter 1/t. Moreover,
the number of additional variables and the number of functions in the PCP of proximity are both bounded by
k 2 , and each function depends on O(t) variables.
The following lemma says that there exists a property that is computable in polynomial time but is hard
to test efficiently in the standard model.
20

Lemma 7.5 ([BHR05]). There exists a property U that is computable in polynomial time but any 31 -test of
which requires at least Ω(n) queries, where n is the input size.
Now we describe the property R that is hard to test when there are adversarial erasures in the input.
Let p(n) be a polynomial bound on the size of a circuit computing U . Let t = ⌊log log log p(n)⌋. Consider a
bit string of length m = n · (p(n))2 . Label the first (n − t)(p(n))2 bits by vi,j where i ∈ [(n − t)(p(n))2 /n]
and j ∈ [n]. Label the remaining bits by wi,j where i ∈ [(p(n))2 ] and j ∈ [t]. The string is said to have the
property R if all of the following conditions hold:
• For each 1 < i ≤ (n − t)(p(n))2 /n and 1 ≤ j ≤ n, we have v1,j = vi,j .
• v1,1 , . . . , v1,n satisfy the property U .
• For every j ∈ [t], the sequence w1,j , . . . , w(p(n))2 ,j is an assignment satisfying the PCP of proximity for
the string v1,1 , . . . , v1,n for property U with distance parameter 1/j.
Theorem 7.6 ([FF06]). Property R can be ε-tested in the standard property testing model using O(1/ε)
queries.
We can prove the following theorem.
Theorem 7.7. There exists some c > 0 such that for all α = Ω( log logn log n ) and ε ∈ [0, 1/4], every α-erasureresilient ε-tester for R makes at least mc queries, where m = n(p(n))2 is the size of the input.
Proof. Assume for the sake of contradiction that there exists an α-erasure-resilient ε-tester for R that makes
fewer than mc queries for all constants c > 0. Let n be such that m = n(p(n))2 and let c′ be such that
′
mc = o(n).
Given an instance v1 , v2 , . . . vn for which we need to test U , we can construct a partially erased string
I of length m = n(p(n))2 as follows. Let t = ⌊log log log p(n)⌋. Let vi,1 , vi,2 , . . . , vi,n be set to the string
v1 , v2 , . . . , vn for all i ∈ [(n − t)(p(n))2 /n], where vi,1 , vi,2 , . . . , vi,n denote the i-th block of n bits in I from
left. Let the remaining bits of I be set to the erased symbol ⊥. A query to this new string can be simulated
by at most one query to the string v1 , v2 , . . . , vn .
If v1 , v2 , . . . , vn satisfies U , then the new string is a Yes instance of R for erasure-resilient testing problem
by the definition of erasure-resilient property testing model. If v1 , v2 , . . . , vn is 13 -far from satisfying U , then
the new string is (1 − nt ) · 31 -far from R, which is at least 14 -far for large enough n. The fraction of erasures
′
in the new string is t/n, which is O( log logn log n ). Therefore, an α-erasure resilient 14 -tester for R making mc
queries for α = Ω( log logn log n ) will yield a 31 -tester for U that makes o(n) queries. This is a contradiction.

7.2

Connections to Distance Approximation Algorithms

Here we discuss the relationship between tolerant testing, defined by Parnas et al. [PRR06], and erasureresilient testing. We define the tolerant property testing model formally in the following.
Definition 7.8 ([PRR06]). An algorithm is said to be an (ε1 , ε2 )-tolerant tester for a property P if, when
given oracle access to a function f , the algorithm (i) accepts with probability at least 2/3 if f is ε1 -close to
P and (ii) rejects with probability at least 2/3 if f is ε2 -far from P, where 0 ≤ ε1 < ε2 ≤ 1. The algorithm
is said to be fully tolerant if it works as above for all ε1 < ε2 , which are given as the inputs.
Tolerant testers are intimately connected to algorithms that approximate the distance of functions to
properties, when given oracle access to the functions. For a property P and a function f , we denote by
εP (f ) the relative Hamming distance of f to P.
Definition 7.9 ([PRR06, FR10]). Let P be a property of functions over D. Let η ≥ 1 and δ ∈ [0, 1). An
algorithm A is said to be an η-distance approximation algorithm with additive error δ for P, if, given oracle
access to a function f , the algorithm outputs, with probability at least 2/3, a value ε̂ such that η1 · εP (f ) − δ ≤
ε̂ ≤ εP (f ). If A works for all δ ∈ [0, 1), we call it an η-distance approximation algorithm.
21

The authors in [PRR06] prove that distance approximation algorithms for a property imply tolerant
testers for the same property. They also show that the existence of fully tolerant testers for a property
implies the existence of distance approximation algorithms for the same property. We will now prove that
the existence of distance approximation algorithms for a property implies the existence of (weak) erasureresilient testers for the same property.
Theorem 7.10. Let A be an η-distance approximation algorithm with additive error δ for a property P of
functions of the form f : D 7→ R. Then there exists an α-erasure-resilient ε-tester A′ that makes the same
number of queries as A and works for all ε, α ∈ (0, 1) satisfying α < ε−δ·η
ε+η .
Proof. Fix an element e ∈ R. Consider the following algorithm A′ . The algorithm A′ , when given oracle
access to an α-erased function g : D 7→ R ∪ {⊥}, queries points from g in the same way as A. Whenever
it queries an erased point, it assumes that the value at that point is e. This way it computes the distance
estimate ε̂ that A would compute if all the erased points had values equal to e. If ε̂ ≤ α, the algorithm
accepts. Otherwise, it rejects.
Let g : D 7→ R ∪ {⊥} be an α-erased function. Let g r : D 7→ R be the restoration of g in which all
erased points are assigned the value e. We can think of A′ as outputting an approximation to εP (g r ). If
g satisfies P, then εP (g r ) ≤ α. Since ε̂ ≤ εP (g r ) with probability at least 2/3, the algorithm will accept
with high probability. If g is ε-far from P, then every restoration of g is ε(1 − α)-far from P, and hence
r
)
εP (g r ) ≥ ε(1 − α). Since ε̂ ≥ εP (g
− δ ≥ ε(1−α)
− δ > α with probability at least 2/3, the algorithm will
η
η
reject with high probability. Note that the last inequality in the above expression follows from the restriction
on α. The theorem follows.
We now revisit the properties discussed in Section 1.2 for which tolerant testers are known and apply Theorem 7.10 to those testers to get erasure-resilient testers. The parameters of these testers are much
worse than what we obtained in previous sections, especially in terms of the restrictions on α.
Corollary 7.11. Let 1 < η < 2. There exists an α-erasure-resilient ε-tester for monotonicity of real-valued
1
1
functions over [n] with query complexity O(( ε(η−1)
)O( η−1 ) · logc n) (where c is a large absolute constant) that
ε
works for all α, ε ∈ (0, 1) such that α < ε+η
.
Corollary 7.12. Let δ ∈ [0, 1]. There existsan α-erasure-resilient
ε-tester for monotonicity of real-valued

log n
d
that works for all α, ε ∈ (0, 1) such that α < (ε − 5δ ·
functions over [n] with query complexity Õ δ4
d2 log n)/(ε + 5d2 log n).

Corollary 7.13. There existsan α-erasure-resilient ε-tester for convexity of real-valued functions over [n]
ε
with query complexity Õ logε n that works for all α, ε ∈ (0, 1) such that α < ε+25
.

8

Conclusions and Open Problems

In this paper, we initiate a study of property testing in the presence of adversarial erasures. We design efficient
erasure-resilient testers for several important properties such as monotonicity, the Lipschitz properties and
convexity over different domains. All our testers for properties of functions on the line domain work for
an arbitrary fraction of erasures. All our testers have only a small additional overhead of O(1/(1 − α)) in
their query complexity in comparison to the query complexity of the currently best, and, in some cases,
optimal, standard testers for the same properties. We also show that not all properties are easy to test in
the erasure-resilient testing model by proving the existence of a property that is easy to test in the standard
model but hard to test in the erasure-resilient model even for a small fraction of erasures. We now list some
open problems.
• We show that tolerant testing is at least as hard as erasure-resilient testing. Determining if tolerant
testing is strictly harder than erasure-resilient testing is an interesting direction.
22

• The fraction of erasures that our monotonicity tester for hypergrid√domains ([n]d ) can tolerate decreases
inversely with d. We also show that an inverse dependence on d is necessary for testers that work
by sampling axis-parallel lines uniformly at random and then test for the property on them. It is an
interesting combinatorial question to determine the exact tradeoff between the fraction of erasures and
the fraction of axis parallel lines that are far from monotone.

Acknowledgments
We thank Jalaj Upadhyay for comments on a draft of this article.

References
[AC06]

Nir Ailon and Bernard Chazelle. Information theory in property testing and monotonicity testing
in higher dimension. Inf. Comput., 204(11):1704–1717, 2006.

[ACCL07] Nir Ailon, Bernard Chazelle, Seshadhri Comandur, and Ding Liu. Estimating the distance to a
monotone function. Random Struct. Algorithms, 31(3):371–383, 2007.
[AJMR16] Pranjal Awasthi, Madhav Jha, Marco Molinaro, and Sofya Raskhodnikova. Testing Lipschitz
functions on hypergrid domains. Algorithmica, 74(3):1055–1081, 2016.
[BBBY12] Maria-Florina Balcan, Eric Blais, Avrim Blum, and Liu Yang. Active property testing. In 53rd
Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick,
NJ, USA, October 20-23, 2012, pages 21–30, 2012.
[BBM12]

Eric Blais, Joshua Brody, and Kevin Matulef. Property testing lower bounds via communication
complexity. Computational Complexity, 21(2):311–358, 2012.

[BCGM12] Jop Briët, Sourav Chakraborty, David Garcı́a-Soriano, and Arie Matsliah. Monotonicity testing
and shortest-path routing on the cube. Combinatorica, 32(1):35–53, 2012.
[BFR+ 13] Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, and Patrick White. Testing
closeness of discrete distributions. J. ACM, 60(1):4, 2013.
[BGH+ 06] Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil P. Vadhan. Robust
PCPs of proximity, shorter PCPs, and applications to coding. SIAM J. Comput., 36(4):889–974,
2006.
[BGJ+ 12] Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, and David P.
Woodruff. Transitive-closure spanners. SIAM J. Comput., 41(6):1380–1425, 2012.
[BHR05]

Eli Ben-Sasson, Prahladh Harsha, and Sofya Raskhodnikova. Some 3CNF properties are hard
to test. SIAM J. Comput., 35(1):1–21, 2005.

[BMR15]

Piotr Berman, Meiram Murzabulatov, and Sofya Raskhodnikova. Testing Convexity of Figures
Under the Uniform Distribution, 2015. To appear in SoCG 2016.

[BRW05]

Tugkan Batu, Ronitt Rubinfeld, and Patrick White. Fast approximate pcps for multidimensional
bin-packing problems. Inf. Comput., 196(1):42–56, 2005.

[BRY14]

Eric Blais, Sofya Raskhodnikova, and Grigory Yaroslavtsev. Lower bounds for testing properties
of functions over hypergrid domains. In IEEE 29th Conference on Computational Complexity,
CCC 2014, Vancouver, BC, Canada, June 11-13, 2014, pages 309–320, 2014.

23

[CDJS15]

Deeparnab Chakrabarty, Kashyap Dixit, Madhav Jha, and C. Seshadhri. Property testing on
product distributions: Optimal testers for bounded derivative properties. In Proceedings of the
Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego,
CA, USA, January 4-6, 2015, pages 1809–1828, 2015.

[CS13]

Deeparnab Chakrabarty and C. Seshadhri. Optimal bounds for monotonicity and lipschitz testing
over hypercubes and hypergrids. In Symposium on Theory of Computing Conference, STOC’13,
Palo Alto, CA, USA, June 1-4, 2013, pages 419–428, 2013.

[CS14]

Deeparnab Chakrabarty and C. Seshadhri. An optimal lower bound for monotonicity testing
over hypergrids. Theory of Computing, 10:453–464, 2014.

[DGL+ 99] 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.
[DJRT13] Kashyap Dixit, Madhav Jha, Sofya Raskhodnikova, and Abhradeep Thakurta. Testing the
lipschitz property over product distributions with applications to data privacy. In TCC, pages
418–436, 2013.
[DRTV16] Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, and Nithin Varma. Erasure-resilient
property testing. In To appear in ICALP 2016, 2016.
[EKK+ 00] Funda Ergün, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld, and Mahesh Viswanathan.
Spot-checkers. J. Comput. Syst. Sci., 60(3):717–751, 2000.
[FF06]

Eldar Fischer and Lance Fortnow. Tolerant versus intolerant testing for boolean properties.
Theory of Computing, 2(9):173–183, 2006.

[Fis04]

E. Fischer. On the strength of comparisons in property testing. Inform. and Comput., 189(1):107–
116, 2004.

[FLN+ 02] Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, and Alex
Samorodnitsky. Monotonicity testing over general poset domains. In Proceedings of the thiryfourth annual ACM symposium on Theory of computing, STOC ’02, pages 474–483, New York,
NY, USA, 2002. ACM.
[FR]

Shahar Fattal and Dana Ron. Approximating the distance to convexity. Unpublished manuscript.
Uploaded at http://www.eng.tau.ac.il/ danar/Public-pdf/app-conv.pdf.

[FR10]

Shahar Fattal and Dana Ron. Approximating the distance to monotonicity in high dimensions.
ACM Transactions on Algorithms, 6(3), 2010.

[GGL+ 00] O. Goldreich, S. Goldwasser, E. Lehman, D. Ron, and A. Samorodnitsky. Testing monotonicity.
Combinatorica, 20:301–337, 2000.
[GGR98]

Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning
and approximation. J. ACM, 45(4):653–750, 1998.

[GK11]

Oded Goldreich and Tali Kaufman. Proximity oblivious testing and the role of invariances. In
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- 14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM
2011, Princeton, NJ, USA, August 17-19, 2011. Proceedings, pages 579–592, 2011.

24

[GR11]

Oded Goldreich and Dana Ron. On proximity-oblivious testing. SIAM J. Comput., 40(2):534–
566, 2011.

[GR16]

Oded Goldreich and Dana Ron. On sample-based testers. ACM Trans. Comput. Theory, 8(2):7:1–
7:54, April 2016.

[GS16]

Oded Goldreich and Igor Shinkar. Two-sided error proximity oblivious testing. Random Struct.
Algorithms, 48(2):341–383, 2016.

[HK08]

Shirley Halevy and Eyal Kushilevitz. Testing monotonicity over graph products. Random Struct.
Algorithms, 33(1):44–67, 2008.

[JR13]

Madhav Jha and Sofya Raskhodnikova. Testing and reconstruction of lipschitz functions with
applications to data privacy. SIAM J. Comput., 42(2):700–731, 2013.

[KR00]

Michael J. Kearns and Dana Ron. Testing problems with sublearning sample complexity. J.
Comput. Syst. Sci., 61(3):428–456, 2000.

[LR01]

E. Lehman and D. Ron. On disjoint chains of subsets. J. Combin. Theory Ser. A, 94(2):399–404,
2001.

[PRR03]

Michal Parnas, Dana Ron, and Ronitt Rubinfeld. On testing convexity and submodularity. SIAM
J. Comput., 32(5):1158–1184, 2003.

[PRR06]

M. Parnas, D. Ron, and R. Rubinfeld. Tolerant property testing and distance approximation. J.
Comput. System Sci., 6(72):1012–1042, 2006.

[Ree03]

Bruce A. Reed. The height of a random binary search tree. J. ACM, 50(3):306–332, 2003.

[RS96]

Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications
to program testing. SIAM J. Comput., 25(2):252–271, 1996.

[SS10]

Michael E. Saks and C. Seshadhri. Estimating the longest increasing sequence in polylogarithmic
time. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010,
October 23-26, 2010, Las Vegas, Nevada, USA, pages 458–467, 2010.

25

