# Property Testing with Online Adversaries

Omri Ben-Eliezer Massachusetts Institute of Technology, Cambridge, MA, USA.
Email<EMAIL_ADDRESS>Esty Kelman Boston University, Boston, MA, USA, and
Massachusetts Institute of Technology, Cambridge, MA, USA. Email:
<EMAIL_ADDRESS>supported by the Computer Science Department, Boston
University. Uri Meir Tel-Aviv University, Tel-Aviv, Israel. Email:
<EMAIL_ADDRESS>Sofya Raskhodnikova Boston University, Boston, MA, USA.
Email<EMAIL_ADDRESS>
###### Abstract

The online manipulation-resilient testing model, proposed by Kalemaj,
Raskhodnikova and Varma (ITCS 2022 and Theory of Computing 2023), studies
property testing in situations where access to the input degrades continuously
and adversarially. Specifically, after each query made by the tester is
answered, the adversary can intervene and either erase or corrupt $t$ data
points. In this work, we investigate a more nuanced version of the online
model in order to overcome old and new impossibility results for the original
model. We start by presenting an optimal tester for linearity and a lower
bound for low-degree testing of Boolean functions in the original model. We
overcome the lower bound by allowing batch queries, where the tester gets a
group of queries answered between manipulations of the data. Our batch size is
small enough so that function values for a single batch on their own give no
information about whether the function is of low degree. Finally, to overcome
the impossibility results of Kalemaj et al. for sortedness and the Lipschitz
property of sequences, we extend the model to include $t<1$, i.e., adversaries
that make less than one erasure per query. For sortedness, we characterize the
rate of erasures for which online testing can be performed, exhibiting a sharp
transition from optimal query complexity to impossibility of testability (with
any number of queries). Our online tester works for a general class of local
properties of sequences. One feature of our results is that we get new (and in
some cases, simpler) optimal algorithms for several properties in the standard
property testing model.

###### Contents

  1. 1 Introduction
    1. 1.1 Our Results and Techniques
      1. 1.1.1 Linearity Testing
      2. 1.1.2 Low-Degree Testing
      3. 1.1.3 Testing Local Properties
    2. 1.2 Related Work on Erasures and Corruptions in Property Testing
    3. 1.3 Connection to Maker-Breaker Games
  2. 2 Preliminaries
    1. 2.1 Online Testing
  3. 3 Linearity Testing
    1. 3.1 An Offline Linearity Test
    2. 3.2 Online-Erasure-Resilient Linearity Tester
    3. 3.3 Probability of Seeing an Erasure
  4. 4 The Lower Bound for Low-Degree Testing
  5. 5 Low-Degree Testing
    1. 5.1 Algebraic Testing Patterns
    2. 5.2 Generalized Witnesses for ${\cal P}_{d}$
    3. 5.3 Soundness of Patterns
    4. 5.4 Algorithm with Batches of $2^{d-1}$ Queries
    5. 5.5 Probability of Seeing an Erasure
    6. 5.6 Analysis of the Online Tester
  6. 6 Online Erasure-Resilient Testing of Local Sequential Properties
    1. 6.1 Online Erasure-Resilience of Pair Tester
    2. 6.2 Pair Tester for Local Properties via Shifted Interval Partitioning
    3. 6.3 Impossibility Result: No Tester for $\omega(\epsilon)$ Erasure Rate
  7. A Observation about Low-Degree Testing with Large Batches
  8. B Proof of Generalized Witness - 5.3

##  1 Introduction

The online manipulation-resilient testing model, proposed by Kalemaj,
Raskhodnikova and Varma [KRV23], studies property testing in contexts where
access to the input is controlled by an adversary and degrades over time.
Their motivation includes situations where access to data is restricted
because of privacy or is misrepresented by someone trying to cover fraud while
having to release some data in response to subpoenas. Another motivation is
testing properties of a massive ever-changing object, where probing the object
affects it. For example, a navigation app might adjust its estimate of which
routes are congested in response to queries. Such situations are plentiful in
data analysis of modern social and transportation networks.

Modeling access to data as degrading adversarially allows the algorithm
designer to ensure that algorithms work in situations where the degradation to
access is too complicated to model accurately or where it is desirable to
avoid relying on distributional assumptions in the algorithm analyses. The
general goal is to understand what properties of the input can be gleaned
without any distributional assumptions, and even in extremely adversarial
regimes, where access to the data or the data itself is manipulated by an
adversary in response to the algorithm’s actions during its execution. From
the theoretical point of view, this investigation sheds light on the structure
of witnesses for different properties.

In the online manipulation-resilient testing model of [KRV23], after each
query to the input object is answered, the adversary can manipulate (i.e.,
erase or corrupt) a fixed number of input values. The input is represented by
a function $f$ on an arbitrary finite domain. The algorithm accesses it by
specifying a query point $x$ in the domain and receiving the answer to the
query from the oracle that represents the current state of the manipulated
input. In addition to allowing us to design fast testers that overcome old and
new lower bounds, studying batch queries is motivated by a connection to
Maker-Breaker games, discussed later (in Section 1.3).

In this work, we investigate a more nuanced version of the online
manipulation-resilient testing model. We allow the adversary to either make
changes at a fixed rate (as in the model of [KRV23]) or accumulate the number
of allowed manipulations in order to utilize them at any subsequent step. We
also study arbitrary rates of erasures in addition to integer rates
investigated by [KRV23], e.g., allowing the adversary to manipulate one point
after every other query. Finally, we also study batch queries, where the
tester gets a group of queries answered between manipulations of the data.

We give online testers for several well studied properties. For Boolean
functions on the domain $\\{0,1\\}^{n}$, we investigate linearity and, more
generally, the class of functions of low degree, that is, of degree at most
$d$ over $\mathbb{F}_{2}$ for specified $d$. (Note that low-degree testing is
equivalent to testing Reed-Muller codes.) For linearity, our online tester has
optimal query complexity. For the degree-$d$ property, we present a lower
bound that nearly matches the upper bound in the concurrent work of Minzer and
Zheng [MZ23] and then show how to overcome the lower bound by using batch
queries. Finally, we consider local properties of functions
$f:[n]\to\mathbb{R}$. (We use $[n]$ to represent
${\left\\{1,2,\dots,n\right\\}}$). Kalemaj et al. proved that two important
properties in that class—sortedness and the Lipschitz property—are not
testable with any number of queries when the adversary erases one point per
query. To overcome this impossibility result, we consider adversaries that
make less than one erasure per query. For sortedness, we characterize the rate
of erasures for which online testing can be performed, exhibiting a sharp
transition from optimal query complexity to impossibility of testability. Our
online tester works for general local properties. Moreover, we show how to
obtain optimal erasure rate with batches of size 2.

Our online testers avoid querying manipulated data by heavily relying on
randomness: the marginal distribution of each query is nearly uniform on a
large subset of the domain. This ensures that each query is unlikely to be a
point previously manipulated by the adversary (for any adversarial strategy).
Consequently, we can separately analyze the probabilities of two important
events: selecting a set of queries that exhibit a violation of the property
(i.e., a _witness_) and querying data modified by the adversary. When
selecting a witness is significantly more likely than encountering a
modification, the tester is likely to find a witness that has not been
tampered with. This approach allows us to design online testers that are
resilient to both erasures and corruptions.

###  1.1 Our Results and Techniques

We study two types of functions: Boolean functions
$f:\\{0,1\\}^{n}\to\\{0,1\\}$ and real-valued functions $f:[n]\to\mathbb{R}$,
i.e., sequences. The testing algorithm gets oracle access to the input
function via one of the specified online adversarial oracles. Initially, the
oracle is identical to the input function. The oracles (formally defined in
Section 2.1) vary in how they are allowed to modify the input. The main
distinctions are erasures vs. arbitrary corruptions (of input values) and when
modifications can occur. In the model of [KRV23], the adversary gets a
parameter $t\in\mathbb{N}$ and is allowed to modify $t$ function values after
answering each query. We call such an adversary _$t$ -online fixed-rate_. We
extend the definition to $t\in\mathbb{R}^{+}$ and also consider _$t$ -online
budget-managing_ adversaries that get allocated $t$ modifications after
answering each query, but can use their allocation at any subsequent time step
in the computation. (See Definition 2.1). Budget-managing adversaries are at
least as powerful as fixed-rate adversaries. But, for some of the properties
we study, we are able to match hardness results for (weaker) fixed-rate
adversaries with algorithms that work even in the presence of (stronger)
budget-managing adversaries.

In addition to the corruption rate $t$, our algorithms get the proximity
parameter $\epsilon\in(0,1),$ as in the standard property testing model, and
have to distinguish functions that have the specified property from functions
that differ in at least an $\epsilon$ fraction of the domain from any function
with the property. See Section 2.1 and Definition 2.4 for formal definitions.

We start our investigation with Boolean functions on the Boolean cube. The
properties we study are linearity and, more generally, of being a polynomial
of degree at most $d$ for a given $d\in\mathbb{N}.$

####  1.1.1 Linearity Testing

Introduced in the pioneering work of [BLR93], linearity testing has been
extensively investigated; see, e.g., [BGLR93, BS94, FGL+96, BCH+96, BGS98,
Tre98, ST98, ST00, HW03, BSVW03, Sam07, ST09, SW06, KLX10, KRV23] and the
survey in [RR16]. A function $f:{{\left\\{0,1\right\\}}^{n}}\to\\{0,1\\}$ is
called _linear_ if $f(x_{1})+f(x_{2})=f(x_{1}\mathbin{\oplus}x_{2})$ for all
$x_{1},x_{2}\in{{\left\\{0,1\right\\}}^{n}},$ where addition is mod 2, and
$\mathbin{\oplus}$ denotes bitwise XOR. We present an optimal tester for
linearity that is resilient to online erasures, as well as online corruptions,
even when the adversary is budget-managing.

######  Theorem 1.1 (Optimal online linearity tester).

There exists a constant $c>0$ such that for all
$n\in\mathbb{N},\epsilon\in(0,1/2]$, and $t$ satisfying $t\log^{2}t\leq
c\cdot\epsilon^{2.5}2^{n/2}$, there exists an $\epsilon$-tester for linearity
of functions $f:\\{0,1\\}^{n}\to\\{0,1\\}$ that works in the presence of a
$t$-online erasure (or corruption) budget-managing adversary and makes
$O\left(\max{\left\\{1/\epsilon,\log t\right\\}}\right)$ queries. In the case
of erasure adversary, the tester has 1-sided error.

In contrast, the linearity tester from [KRV23] works for a smaller range of
$t$ (specifically, $t\leq c_{0}\cdot\epsilon^{5/4}2^{n/4}$ for some constant
$c_{0}$) and makes
$O\big{(}\min\big{(}\frac{1}{\epsilon}\log\frac{t}{\epsilon},\frac{t}{\epsilon}\big{)}\big{)}$
queries.

The linearity tester in Theorem 1.1 has optimal query complexity both for
fixed-rate and budget-managing adversaries, in the case of erasures (and,
consequently, in the more challenging setting with corruptions). This follows
from the known query lower bounds of $\Omega\left(1/\epsilon\right)$ with no
erasures and $\Omega(\log t)$ for fixed-rate adversarial erasures [KRV23,
Theorem 1.4]).

Our online linearity tester improves on the tester in [KRV23] both in terms of
query complexity and in terms of simplicity of the tester. The classical
linearity test of [BLR93] looks for witnesses of nonlinearity consisting of
three points $x_{1},x_{2}$ and $x_{1}\mathbin{\oplus}x_{2}$ that satisfy
$f(x_{1})+f(x_{2})\neq f(x_{1}\mathbin{\oplus}x_{2})$. Kalemaj et al.
generalized it to witnesses consisting of any even number of points and their
XOR. Let $\text{\sc XorTest}_{k}$ denote the test that picks $k$ points
uniformly at random and checks if these points and their XOR form a witness of
nonlinarity. We improve upon the soundness analysis of this test and use it to
get an optimal online-erasure-resilient linearity tester. Specifically, in
Lemma 3.1, we show that $\text{\sc XorTest}_{k}$ rejects every function that
is $\epsilon$-far from linearity with probability proportional to $k\epsilon$
(as long as $k\epsilon$ is at most a small constant). It implies that
$\text{\sc XorTest}_{k}$ can be used in the standard linearity testing setting
(without erasures) to obtain another optimal $O(1/\epsilon)$-query tester:
$\text{\sc XorTest}_{k}$ can be repeated $O(1/(k\epsilon))$ times to obtain
constant probability of error. To the best of our knowledge, only testers
based on the BLR test (i.e., $\text{\sc XorTest}_{2}$) have been analyzed in
the standard linearity testing setting.

Another important ingredient in the analysis of our online linearity tester is
bounding the probability of seeing an erasure. A good bound for this event
ensures that our tester is resilient to corruptions (not just erasures). It
also allows us to obtain a clean online tester that is based on multiple
simulations of $\text{\sc XorTest}_{k}$, where each simulation initially
samples $2k$ points to fool the adversary and then selects a random subset of
size $k$ for the XOR as the final query. In contrast, the online linearity
tester of [KRV23] is more complicated: it relies on work investment strategy.

####  1.1.2 Low-Degree Testing

Low-degree testing, equivalent to local testing of Reed-Muller codes, is a
natural generalization of linearity testing. It has been investigated, e.g.,
in [BFL91, BFLS91, GLR+91, FGL+96, FS95, RS96, RS97, AKK+05, AS03, MR08,
Mos17, KR06, Sam07, ST09, JPRZ09, BKS+10, HSS13, RS13, DG13, KM22, KRV23]. For
a $d\in\mathbb{N}$, let ${\cal P}_{d}$ denote the set of all polynomials
$p:\\{0,1\\}^{n}\to\\{0,1\\}$ of degree at most $d$, that is, functions $p(x)$
that can be represented as a sum of monomials111To be consistent with previous
work, we allow $S=\emptyset$. The property ${\cal P}_{1}$ is _affinity_ , and
linear functions (discussed in Section 1.1.1) are affine with the additional
requirement that the constant in the polynomial representation is 0. of the
form $\prod_{i\in S}x[i]$, where $x=(x[1],\dots,x[n])$ is a vector of $n$ bits
and $|S|\leq d$. In the standard property testing model, ${\cal P}_{d}$ can be
$\epsilon$-tested with $O(1/\epsilon+2^{d})$ queries by repeating the
following test of Alon et al. [AKK+05]: select $d+1$ points in $\\{0,1\\}^{n}$
uniformly at random, query all of their linear combinations $f$, and accept
iff the sum of the returned values is 0. This tester was analyzed by Alon et
al. [AKK+05], with an asymptotic improvement by Bhattacharyya et al. [BKS+10],
and the matching lower bound of $\Omega(1/\epsilon+2^{d})$ on query complexity
was proved in [AKK+05].

As $d$ grows, the test of Alon et al. becomes more structured: the number of
points queried is exponential in the number of points selected at random. This
makes it hard to adapt to the online model, since the adversary can predict
and erase the points needed by the tester. We show that there is an underlying
reason for this difficulty: low-degree testing for $d>1$ is strictly harder
than testing linearity in terms of the dependence on $t$, the rate of
erasures.

######  Theorem 1.2 (Lower bound for low-degree testing).

Fix an integer $d>1$, and let ${\cal P}_{d}$ be the property of being a
polynomial of degree at most $d$ over $\mathbb{F}_{2}$. There exists
$n_{0}=n_{0}(d)$, such that for all $n\geq n_{0}$ and $\epsilon\in(0,1/3]$,
every $\epsilon$-tester of functions $f\colon\\{0,1\\}^{n}\to\\{0,1\\}$ for
${\cal P}_{d}$ that works in the presence of a $t$-online fixed-rate erasure
adversary must make $\Omega\left(\log^{d}t\right)$ queries.

Our lower bound is nearly tight in terms of the dependence on $t$ and $d$: in
a concurrent work, Minzer and Zheng [MZ23] show that ${\cal P}_{d}$ can be
tested with $O\left(\frac{1}{\epsilon}\log^{3d+3}\frac{t}{\epsilon}\right)$
queries with $t$-online fixed-rate erasure adversaries. Thus, the query
complexity of ${\cal P}_{d}$ is $\log^{\Theta(d)}t$ (for constant $\epsilon$).

To prove our lower bound, we define an extended representation ${\sf
Ext}_{d}(x)$ for each vector $x\in\mathbb{F}_{2}^{n}$, where each entry of
${\sf Ext}_{d}(x)$ is an evaluation of a monomial of degree at most $d$ on
input $x$. We consider the adversarial strategy of erasing function values on
all points whose extended representations are in the span of the extended
representations of previous queries. We use [BEHL12, Lemma 1.4] (or,
equivalently, [KS05, Theorem 1.5]) to demonstrate that when the number of
queries is, roughly, at most $\binom{\log t}{d}$, the adversary can
successfully execute this strategy. Finally, we apply Yao’s minimax principle
to show that in this case no online tester can distinguish random polynomials
of degree $d$ from random functions.

We overcome the lower bound by allowing batch queries, where the tester gets a
group of $b$ queries answered between manipulations of the data. The original
model corresponds to $b=1$. Since the atomic tester of Alon et al. makes
$2^{d+1}$ queries, it can be used directly in an online tester with batch size
$b=2^{d+1},$ achieving query complexity $O(\frac{1}{\epsilon}+2^{d})$, the
same as in the offline regime. For completeness, in Appendix A, we analyze the
rate of erasures $t$ achievable in this setting. It is natural to ask for
which batch sizes we can achieve overhead polynomial in $d\log t$ over the
offline query complexity. We show how to do it for $b=2^{d-1}$, i.e., with the
batch size equal to one quarter of the points needed for the smallest witness
of not satisfying ${\cal P}_{d}.$ In particular, for quadraticity, it
corresponds to batches of size $b=2$, a natural extension of testing linearity
with batches of size 1.

######  Theorem 1.3.

There exists a constant $c>0$ such that for all $n,d\in\mathbb{N},\
\epsilon\in(0,1/2)$, and $t$ satisfying $d<n/11$ and $t\log^{7}t\leq
c\cdot\epsilon^{2.5}d^{-7}2^{(n-11d)/2}$, there exists an $\epsilon$-tester
for property ${\cal P}_{d}$ of functions $f:\\{0,1\\}^{n}\to\\{0,1\\}$ that
works in the presence of a $(2^{d-1},t)$-online erasure budget-managing
adversary and makes $O\left(1/\epsilon+2^{3d}\left(d+\log t\right)^{3}\right)$
queries.

Our online low-degree tester is a natural generalization of our linearity
tester and of the tester of [AKK+05]. The witnesses we consider generalize the
$(d+1)$-dimensional cubes formed by the points queried by the tester of
[AKK+05] to _chains of cubes_ (see Figure 1).

We show chains of cubes are viable witnesses as they are a special case of
_$k$ -local characterizations_ defined in the seminal work of Kaufman and
Sudan [KS08] on algebraic property testing. In addition, our _chains-of-cubes_
test shares important features with the test of Alon et al. This allows us to
show, by generalizing an argument from [BKS+10], that for small values of
$\epsilon$, the probability of seeing a violation increases linearly in the
size of the witness.

To test with a chain of cubes, the tester first declares $d-1$ directions that
form a linear subspace $A$. Then, intuitively, it runs our online linearity
tester, replacing each query $x$ with a batch query $x+A$ (all points in this
affine subspace). To analyze erasure resilience, whenever the adversary erases
point $x,$ we allow it to erase the entire space $x+A$ for free. This allows
us to analyze the probability of seeing an erasure over the quotient group
$\mathbb{F}_{2}^{n}/A$, which is isomorphic to $\mathbb{F}_{2}^{n-d+1}$,
essentially reducing the analysis to that of the online linearity tester
(because, over this space, each query and erasure are of a single point).

####  1.1.3 Testing Local Properties

Next we investigate properties of sequences, represented by functions
$f:[n]\to\mathbb{R}$. Kalemaj et al. showed that two fundamental properties of
sequences, _sortedness_ and the _Lipschitz property_ , are not testable with
any number of queries in the presence of a fixed-rate adversary making $t=1$
erasures per query. Are these properties testable in models with fewer
erasures than queries?

We explore this question in depth. The answer is generally positive, but
differs between the two adversarial manipulation models we study: fixed-rate
and budget-managing. Our results are optimal, and the query complexity in many
regimes matches that of the standard (offline) property testing model. Our
online testers work in the general framework of local properties [Ben19].

Before stating our results, we define sortedness, the Lipschitz property, and
the general class of local properties. A sequence $f:[n]\to\mathbb{R}$ is
sorted if $f(x)\leq f(y)$ for all $x<y$, where $x,y\in[n]$. Sortedness is one
of the most investigated properties in the context of property testing (see
[EKK+00, DGL+99, Ras99, BGJ+12, CS13, Bel18, PRV18] and the survey in
[Ras16]). A sequence $f:[n]\to\mathbb{R}$ is Lipschitz if $|f(x+1)-f(x)|\leq
1$ for all $x\in[n-1]$. The Lipschitz property has been studied in [JR13,
CS13, DJRT13, BRY14, AJMR16, CDJS17] and has applications to data privacy.
Both sortedness and the Lipschitz property belong to the class of local
properties, defined by [Ben19]. A property ${\cal P}$ of sequences
$f\colon[n]\to\mathbb{R}$ is _local_ 222This class of properties is called
2-local in [Ben19], where more general $k$-local properties are defined as
characterized by families of forbidden $k$-tuples. For simplicity and clarity
of exposition, we focus on 2-local properties, but our results easily
generalize to $k$-local properties (with increased batch sizes). if there
exists a family ${\cal F}$ of _forbidden_ pairs $(a,b)\in\mathbb{R}^{2}$ such
that

$f\in\mathcal{P}$ $\Leftrightarrow$ $\forall i\in[n-1]\
\forall(a,b)\in\mathcal{F}\colon(f(i),f(i+1))\neq(a,b)$.

Then we say that $\mathcal{P}$ is characterized by the family $\mathcal{F}$.
Sortedness is characterized by ${\cal F}=\\{(a,b):a>b\\}$; that is, a sequence
is sorted if and only if it does not contain a pair of _consecutive_ elements
with decreasing values. The Lipschitz property is characterized by ${\cal
F}=\\{(a,b):|a-b|>1\\}$.

##### Results for batch size $b=1$.

We give tight bounds on the rate of erasures and corruptions online algorithms
can handle in the presence of _budget-managing_ adversaries.

######  Theorem 1.4 (Testing local properties in presence of budget-managing
adversary with batch size $1$).

There exist absolute constants $0<c<C$ satisfying the following. For all
$\epsilon>0$ and $n\geq C/\epsilon$:

  1. 1.

For every local property $\mathcal{P}$ of sequences $f\colon[n]\to\mathbb{R}$,
and every $t\leq c\epsilon$, there exists an $\epsilon$-tester for
$\mathcal{P}$ that works in the presence of a $t$-online erasure budget-
managing adversary and makes $O\big{(}\frac{\log(\epsilon
n)}{\epsilon}\big{)}$ queries.

  2. 2.

For every $t\geq C\epsilon$, there is no $\epsilon$-tester for sortedness of
sequences $f\colon[n]\to\mathbb{R}$ that works in the presence of a $t$-online
erasure budget-managing adversary (with any number of queries).

Both of these results hold (with the same parameters) if erasures are replaced
with corruptions. In the case of erasure adversary, the tester has one-sided
error.

The positive result in Item 1 of Theorem 1.4 matches the query complexity of
the offline optimal tester from [Ben19] while also attaining optimal
resilience guarantees.

Theorem 1.4 highlights a dramatic phase transition in the threshold regime
where $t=\Theta(\epsilon)$: when $t=\omega(\epsilon)$, sortedness is not
testable at all; whereas when $t=o(\epsilon)$, it is testable (and in fact,
all local properties are testable) with offline-optimal query complexity!

For fixed-rate adversaries, the threshold rate is arbitrarily close to $1$.
The negative result is established in [KRV23]; the positive result is stated
in 6.5 and proved in Section 6.

##### Results for batch size $b=2$.

For batch size one, we have seen that the threshold rate for sortedness in the
presence of a budget-managing adversary is $\Theta(\epsilon)$, i.e., less than
one. Batches of size two result in a dramatically different picture: we can
tolerate as many as $\tilde{\Omega}(n)$ erasures or corruptions between
consecutive batches while maintaining optimal query complexity!

######  Theorem 1.5.

There exists $c>0$ satisfying the following. Let $\epsilon>0$ and
$n\in\mathbb{N}$. For every local property $\mathcal{P}$ of sequences
$f\colon[n]\to\mathbb{R}$, and every
$t\leq\frac{c\epsilon^{2}n}{\log^{2}\epsilon n}$, there exists an
$\epsilon$-tester for $\mathcal{P}$ with batch size $b=2$ that works in the
presence of a $t$-online erasure (or corruption) budget-managing adversary and
makes $O\big{(}\frac{\log(\epsilon n)}{\epsilon}\big{)}$ queries. In the case
of erasures, the tester has one-sided error.

##### Technical overview: Pair tester for local properties.

Our main technical contribution here shows that a simple and generic pair
tester (see Algorithm 5 and Lemma 6.2), which queries $f$ on pairs of the form
$(x,x+2^{i})\in[n]^{2}$, works for all local properties of sequences in the
_offline_ property testing model, with query complexity of
$O\big{(}\frac{\log(\epsilon n)}{\epsilon}\big{)}$. This matches known lower
bounds on the query complexity of sortedness [CS14, Bel18]. Our upper bound is
the same as that obtained in [Ben19], but the new (pair) tester is simpler and
has the additional feature of being resilient to online manipulations.
Notably, there exist pair testers which obtain this query complexity for
specific classes of local properties; see, e.g., the work of Chakrabarty,
Dixit, Jha, and Seshadhri [CDJS17] on bounded derivative properties. Our work
generalizes this result to all local properties of sequences. The proof
proposes and analyzes a randomly-shifted variant of Ben-Eliezer’s generic
tester for local properties [Ben19], and shows that this more structured
tester can be simulated by a pair tester.

We show that the pair tester is online erasure-resilient (and corruption-
resilient) in a strong sense: with good probability it never queries
previously manipulated elements. The analysis distinguishes between two types
of erasures: ones that happen after the first element of a pair is queried,
but before the second element; and all other erasures. Roughly speaking, the
sharp distinction in the erasure thresholds between batch size $b=1$ and $b=2$
exists since the first type of erasures, which is only available to the
adversary when $b=1$, is substantially more effective than the second type in
hiding information.

###  1.2 Related Work on Erasures and Corruptions in Property Testing

Erasure-resilient testing was first investigated by Dixit et al. [DRTV18] in
an offline model. In the model of Dixit et al., also studied in [RV18, RRV21,
BFLR20, PRW22, LPRV21, NV21], the adversary performs all erasures to the
function before the execution of the algorithm.

As discussed, the online testing model was defined in [KRV23]. In addition to
the results already mentioned, [KRV23] gave an online $\epsilon$-tester for
quadraticity of functions $f:\\{0,1\\}^{n}\to\\{0,1\\}$ that has query
complexity $O(1/\epsilon)$ for constant erasure rate $t.$ The dependence on
$t$ in the query complexity was doubly exponential, and it was left open to
obtain a quadraticity tester that can deal with corruptions. In a concurrent
work, Minzer and Zheng [MZ23] improve the quadraticity tester and vastly
generalize it to deal with all low-degree properties ${\cal P}_{d}$ over
general fields $\mathbb{F}_{q}$. Their tester works in the presence of
$t$-online fixed-rate erasure adversaries and makes
$O\left(\frac{1}{\epsilon}\log^{3d+3}\frac{t}{\epsilon}\right)$ queries when
$q$ is a prime and $q^{O(1)}\cdot
O\left(\frac{1}{\epsilon}\log^{3d+3q}\frac{t}{\epsilon}\right)$ queries when
$q$ is a prime power.

##### Testing in dynamic environments.

Another related line of work is on property testing in dynamic environments
(see, e.g., [GR17, NR21]), which considers settings where the tested object
undergoes changes independent of the actions taken by the tester. The
(adversarial) online testing model extends the study of dynamic settings to
regimes where the data in the object, or the access to the data, may change
continuously in response to the actions of the tester.

###  1.3 Connection to Maker-Breaker Games

Positional games are a central and widely investigated topic in the modern
combinatorics literature; see, e.g., the standard textbooks on this topic
[Bec08, HKSS14]. Property testing in the online erasure model is closely
related to positional games, and in particular to the most prominent and well
studied example of positional games: _Maker-Breaker games_. Even though
Kalemaj et al. described their quadraticity tester as a game, they did not
discuss the connection to the Maker-Breaker literature.

A Maker-Breaker game is defined by a finite set $X$ of board elements and a
family ${\cal W}\subseteq 2^{X}$ of winning sets. In an $(s:t)$ Maker-Breaker
game, two players, called Maker and Breaker, take turns in claiming previously
unclaimed elements of $X$. On each turn, Maker claims $s$ board elements,
whereas Breaker claims $t$ elements. Maker wins the game if she manages to
claim all elements of some winning set; otherwise, Breaker wins.

In online testing, the algorithm plays the role of Maker and the adversary is
Breaker. The set $X$ is the domain of the function, and the winning sets are
witnesses, i.e., tuples of points that demonstrate that the function does not
have the property. A big complication is that the tester does not know in
advance which sets are in ${\cal W}$. A prerequisite for designing an online
tester is being able to identify the general structure of the sets in ${\cal
W}$ and a winning strategy for Maker. For example, Kalemaj et al. build their
tester for quadraticity by identifying a winning strategy for a game where
${\cal W}$ consists of “cubes” of the form $(x,y,z,x+y,x+z,y+z,x+y+z)$. Our
low-degree tester (for the special case of quadraticity) uses more intricate
winning sets; see the discussion of patterns in Section 5.

Note that the original online model corresponds to $(1:t)$ Maker-Breaker
games, whereas the version with batches of size $b$ corresponds to general
$(b:t)$ Maker-Breaker games. This provides additional motivation to study
batches. Going in the other direction, we hope that online testing inspires
new research on Maker-Breaker games. A lot of the current literature on
positional games focuses on the case where the board is a complete graph and
the winning sets are graph-related (e.g., cliques). Examples from online
property testing may motivate new research on Maker-Breaker games with
emphasis on other types of boards, such as the hypercube.

##  2 Preliminaries

##### Notation.

We use $[n]$ to represent ${\left\\{1,2,\dots,n\right\\}}$ and $\log$ to
denote logarithm base 2. Let ${\cal P}_{d}$ be the class of Boolean functions
$f:{\left\\{0,1\right\\}}^{n}\to{\left\\{0,1\right\\}}$ of degree at most $d$
over $\mathbb{F}_{2}$.

###  2.1 Online Testing

We model access to the input with a sequence
${\left\\{\mathcal{O}_{i}\right\\}}_{i\in{\mathbb{N}}}$ of oracles, where
$\mathcal{O}_{i}$ is used to answer the $i$-th query (or, more generally, the
$i$-th batch of queries). Oracle $\mathcal{O}_{1}$ gives access to the
original input (e.g., when the input is a function $f$, we have
$\mathcal{O}_{1}\equiv f$). Subsequent oracles are objects of the same type as
the input (e.g., functions with the same domain and range). Each such oracle
is obtained by the adversary by modifying the previous oracle to include a
growing number of erasures/corruptions as $i$ increases. We use
${\text{Dist}}(\mathcal{O},\mathcal{O}^{\prime})$ for the Hamming distance
between the two oracles (i.e., the number of queries for which they give
different answers). We let $t\in\mathbb{R}_{\geq 0}$ denote the number of
_erasures_ (or _corruptions_) _per query_ (or a batch of queries).

######  Definition 2.1 (Fixed-rate and budget-managing adversaries).

Fix a parameter $t>0$. A sequence333Our algorithms only access a finite
subsequence of this sequence. of oracles
$\mathcal{O}={\left\\{\mathcal{O}_{i}\right\\}}_{i\in{\mathbb{N}}}$ is induced
by a _$t$ -online fixed-rate adversary_ if $\mathcal{O}_{1}$ is equal to the
input and, for all $i\in\mathbb{N}$,

$Dist(\mathcal{O}_{i},\mathcal{O}_{i+1})\leq\left\lfloor{(i+1)\cdot
t}\right\rfloor-\left\lfloor{i\cdot t}\right\rfloor.$

A sequence of oracles
$\mathcal{O}={\left\\{\mathcal{O}_{i}\right\\}}_{i\in{\mathbb{N}}}$ is induced
by a _$t$ -online budget-managing adversary_ if $\mathcal{O}_{1}$ is equal to
the input and, for all $i\in\mathbb{N}$,

${\text{Dist}}(\mathcal{O}_{1},\mathcal{O}_{i+1})\leq i\cdot t.$

Note that a budget-managing adversary has more power: an oracle sequence that
can be induced by a $t$-online fixed-rate adversary can also be induced by a
$t$-online budget managing adversary.

######  Definition 2.2 (Batch-$b$ adversary).

Fix $b\in\mathbb{N}.$ A _batch- $b$ adversary_ uses oracle $\mathcal{O}_{1}$
to answer the first $b$ queries and, more generally, oracle $\mathcal{O}_{i}$
to answer the $i$-th batch of $b$ queries. By default (if $b$ is not
specified), we assume $b=1.$

Our complexity measure is always the total number of queries, regardless of
the batch size $b$. Finally, we consider two types of manipulations to the
input: erasures and corruptions.

######  Definition 2.3 (Erasure and corruption adversaries).

Let $\perp$ represent the erasure symbol. A sequence of oracles
$\mathcal{O}={\left\\{\mathcal{O}_{i}\right\\}}_{i\in{\mathbb{N}}}$ is induced
by an _erasure adversary_ if for all $i\in\mathbb{N}$ and data points $x$,

$\mathcal{O}_{i+1}(x)\in{\left\\{\mathcal{O}_{i}(x),\perp\right\\}}.$

A _corruption adversary_ can change answers to anything in the range, i.e.,
$\mathcal{O}_{i}$ can be any valid input for the computational task at hand.

A property ${\cal P}$ denotes a set of objects (typically, a set of
functions). Intuitively, it represents the set of positive instances for the
testing problem. The (relative Hamming) distance between a function $f$ and a
property ${\cal P}$, denoted $dist(f,{\cal P})$, is the smallest fraction of
function values of $f$ that must be changed to obtain a function in ${\cal
P}.$ Given a proximity parameter $\epsilon\in(0,1)$, we say that $f$ is
_$\epsilon$ -far_ from ${\cal P}$ if $dist(f,{\cal P})\geq\epsilon.$ An online
tester is given a proximity parameter $\epsilon$ and, in addition, one or two
parameters that characterize its adversary: the rate of erasures (or
corruptions) $t$ and (optionally) the batch size $b.$

######  Definition 2.4 (Online $\epsilon$-tester).

Fix $\epsilon\in(0,1).$ An online $\epsilon$-tester ${\cal T}$ for a property
$\mathcal{P}$ that works in the presence of a specified adversary (e.g.,
$t$-online batch-$b$ erasure budget-managing adversary) is given access to to
an input function $f$ via a sequence of oracles
$\mathcal{O}={\left\\{\mathcal{O}_{i}\right\\}}_{i\in{\mathbb{N}}}$ induced by
that type of adversary. For all adversarial strategies of the specified type,

  1. 1.

if $f\in\mathcal{P}$, then ${\cal T}$ accepts with probability at least 2/3,
and

  2. 2.

if $f$ is $\epsilon$-far from ${\cal P},$ then ${\cal T}$ rejects with
probability at least 2/3,

where the probability is taken over the random coins of the tester. If ${\cal
T}$ works in the presence of an erasure (resp., corruption) adversary, we
refer to it as an online-erasure-resilient (resp., online-corruption-
resilient) tester.

If ${\cal T}$ always accepts all functions $f\in{\cal P}$, then it has
_1-sided error._ If $\mathcal{T}$ chooses its queries in advance, before
observing any outputs from the oracle, then it is _nonadaptive_.

To ease notation, we use $\mathcal{O}(x)$ for the oracle’s answer to query $x$
(omitting the timestamp $i$). If $x$ was queried multiple times,
$\mathcal{O}(x)$ denotes the first answer given by the oracle.

##  3 Linearity Testing

This section is dedicated to proving Theorem 1.1. We first analyze an
_offline_ tester which we later simulate as part of our main algorithm. Since
it uses Fourier analysis, here we use the standard notation switch for the
value returned by a Boolean function (see, e.g., [O’D14]), where true is
denoted by -1 and false is denoted by 1. As a result, the input function is of
the form $f\colon\\{0,1\\}^{n}\to\\{-1,1\\}$, and it is linear if
$f(x_{1})\cdot f(x_{2})=f(x_{1}\mathbin{\oplus}x_{2})$ for all
$x_{1},x_{2}\in{{\left\\{0,1\right\\}}^{n}}.$

###  3.1 An Offline Linearity Test

We first define $\text{\sc XorTest}_{k}$, introduced by [KRV23], which
naturally extends the BLR test.

Input : Even integer parameter $k\geq 2$ and query access to a function
$f:\\{0,1\\}^{n}\to\\{-1,1\\}$

1 Query $k$ points $x_{1},\dots,x_{k}\in{{\left\\{0,1\right\\}}^{n}}$ chosen
uniformly at random (with replacement).

2 Query point $y=\mathbin{\bigoplus}_{i\in[k]}x_{i}$.

Accept if $f(y)=\prod_{i\in[k]}f(x_{i})$ (equivalently, if
$f(y)\cdot\prod_{i\in[k]}f(x_{i})=1$); otherwise, reject.

Algorithm 1 $\text{\sc XorTest}_{k}$

The test always accepts all linear functions, as can be shown by induction on
$k$. The next lemma demonstrates that $\text{\sc XorTest}_{k}$ rejects
functions that are $\epsilon$-far from linear with sufficient probability.
This is a strengthening of [KRV23, Theorem 1.2], which bounded the rejection
probability by $\epsilon.$

######  Lemma 3.1.

If $f$ is $\epsilon$-far from linear, and $k\geq 2$ is even, then

$\displaystyle{\Pr\left[{\text{\sc XorTest}_{k}(f)\text{\em\
rejects}}\right]}\geq\frac{1-(1-2\epsilon)^{k-1}}{2}\geq\min\Big{\\{}\frac{1}{4}\,,\,\frac{k\epsilon}{2}\Big{\\}}.$

Since $k\geq 2$ and $\epsilon\in(0,1/2]$, we get $(1-2\epsilon)^{k-1}\leq
1-2\epsilon$, with the first inequality in the lemma yielding the bound proved
in [KRV23]. However, as it is imperative to use $k>2$, the strengthened bound
is crucial in obtaining an optimal online-erasure-resilient tester. In
addition, the stronger guarantee we prove suffices to obtain new optimal
offline linearity testers by repeating Algorithm 1; this can be done with any
value of $k$ from $3$ to $O(1/\epsilon)$.

###### Proof of Lemma 3.1..

The key tool used in the proof is Fourier analysis (see, e.g., [O’D14] for an
overview of the technique and standard facts). We start by giving a couple of
standard definitions.

The _character_ functions $\chi_{S}\colon\\{0,1\\}^{n}\to\\{-1,1\\}$, defined
as $\chi_{S}=(-1)^{\sum_{i\in S}x_{i}}$ for $S\subseteq[n]$, form an
orthonormal basis for the space of all real-valued functions on
$\\{0,1\\}^{n}$ equipped with the inner-product $\langle
g,h\rangle=\underset{x\sim\\{0,1\\}^{n}}{\mathbb{E}}[g(x)h(x)],$ where
$g,h\colon\\{0,1\\}^{n}\to\mathbb{R}$. For $g\colon\\{0,1\\}^{d}\to\mathbb{R}$
and $S\subseteq[n]$, the Fourier coefficient of $g$ on $S$ is
$\widehat{g}(S)=\langle
g,\chi_{S}\rangle=\underset{x\sim\\{0,1\\}^{n}}{\mathbb{E}}[g(x)\chi_{S}(x)].$

Now consider a function $f:\\{0,1\\}^{n}\to\\{-1,1\\}$ that is $\epsilon$-far
from linear. It is well known that the distance from $f$ to linearity is
$\frac{1}{2}-\frac{1}{2}\max_{S\subseteq[n]}\widehat{f}(S).$ Since the
distance is at least $\epsilon$, we get

$\displaystyle\max_{S\subseteq[n]}\widehat{f}(S)\leq 1-2\epsilon.$ (1)

As shown in [KRV23, Equation (4)],

$\displaystyle{\Pr\left[{\text{\sc XorTest}_{k}(f)\text{\em\
rejects}}\right]}$
$\displaystyle=\underset{x_{1},\dots,x_{k}\sim\\{0,1\\}^{n}}{\mathbb{E}}\Big{[}\frac{1}{2}-\frac{1}{2}\prod_{i\in[k]}f(x_{i})\cdot
f\left(\mathbin{\oplus}_{i=1}^{k}x_{i}\right)\Big{]}$
$\displaystyle=\frac{1}{2}-\frac{1}{2}\sum_{S\subseteq[n]}\widehat{f}(S)^{k+1}.$
(2)

Next, we bound the sum in (2) in terms of $\max_{S\subseteq[n]}\widehat{f}(S)$
and then apply (1):

$\displaystyle\sum_{S\subseteq[n]}{\widehat{f}{\left({S}\right)}}^{k+1}\leq\max_{S\subseteq[n]}{\widehat{f}{\left({S}\right)}}^{k-1}\cdot\sum_{S\subseteq[n]}{\widehat{f}{\left({S}\right)}}^{2}$
$\displaystyle=\max_{S\subseteq[n]}{\widehat{f}{\left({S}\right)}}^{k-1}\leq(1-2\epsilon)^{k-1}.$

Substituting this expression into (2), we obtain the first inequality in Lemma
3.1. To obtain the second inequality in Lemma 3.1, we show that
$1-(1-2\epsilon)^{k-1}$ is at least $1/2$ for large values of $k$ and at least
$k\epsilon$ for small values of $k\geq 2$. The bound holds trivially for
$\epsilon=1/2$, so from now on assume $\epsilon<1/2$. Let $k_{0}\in\mathbb{R}$
be such that $(1-2\epsilon)^{k_{0}-1}=1/2$. If $k\geq k_{0}$, we have

$1-(1-2\epsilon)^{k-1}\geq 1-(1-2\epsilon)^{k_{0}-1}=1/2.$

For the case $k\in[2,k_{0})$, we prove by induction on $k$ that
$1-(1-2\epsilon)^{k-1}\geq k\epsilon$. For $k=2$, equality holds. For each
$k\in[3,k_{0})$, we have

$1-(1-2\epsilon)^{k-1}=\big{(}1-(1-2\epsilon)^{k-2}\big{)}+2\epsilon(1-2\epsilon)^{k-2}\geq(k-1)\epsilon+2\epsilon\cdot(1-2\epsilon)^{k_{0}-1}=k\epsilon,$

where for the inequality we bound the first term by the inductive hypothesis
on $k-1$ and the second term using $k-2\leq k_{0}-1$. Thus, in both cases, at
least one of the expressions in the minimum is a lower bound. ∎

###  3.2 Online-Erasure-Resilient Linearity Tester

Our algorithm (Algorithm 2) is based on multiple simulations of $\text{\sc
XorTest}_{k}$. Each simulation starts by querying a reserve of $m=2k$ initial
points to keep many possibilities open for the final $\text{\sc XorTest}_{k}$
query. Specifically, a reserve of $2k$ random points creates roughly $2^{2k}$
different options for the final $\text{\sc XorTest}_{k}$ query444In [KRV23],
the reserve is used to simulate $\text{\sc XorTest}_{k}$ with different values
of $k$. Fixing the value of $k$ to half of the reserve size eases our analysis
(allowing us to use Lemma 3.1 with the same $k$) while providing many
options.. We set $m$ to about $\log t$ to ensure that a significant fraction
of options remains open before the final query of the $\text{\sc XorTest}_{k}$
simulation is made. There is also a small additional dependence on $\epsilon$
to overcome the fact that the overall number of iterations depends on
$\epsilon$ and, as a result, for some settings of parameters, the probability
of error in each iteration has to be proportional to $\epsilon.$ In principle,
setting $m=\Theta(\log t+1/\epsilon)$ and the number of iterations, $r$, to
$\Theta(1)$ is enough for the desired query complexity, but it significantly
restricts the range of parameters (e.g., it only works when $\epsilon\geq
2/n$). Our choice of parameters is more subtle: besides ensuring optimal query
complexity, it enlarges the range of $\epsilon$ and $t$ (in Theorem 1.1) for
which Algorithm 2 is applicable. To do this, we set $m$ to a smaller value:
$\log t+o(\log t)+\Theta(\log(1/\epsilon))$, and the number of iterations,
$r$, depends on $\epsilon$ and $m$.

Input : Parameters $\epsilon\in(0,1/2],t\in\mathbb{N}$; query access to $f$
via $t$-erasure oracle sequence $\mathcal{O}$

1 $t\leftarrow\max\\{t,2\\}$ $\triangleright$ If $t<2$, replace it with $t=2.$

2 $m\leftarrow 4\Big{\lceil}{\frac{1}{4}\big{(}14+\log
t+\log\log^{2}t+\log\frac{1}{\epsilon^{2}}}\big{)}\Big{\rceil}$,
$\alpha\leftarrow\min\big{\\{}\frac{1}{4},\frac{m\epsilon}{4}\big{\\}}$ and,
$r\leftarrow\left\lceil{\frac{5}{4\alpha}}\right\rceil$.

3 repeat  _$r$_ times

4 Sample $X=(x_{1},\dots,x_{m})\in({{\left\\{0,1\right\\}}^{n}})^{m}$
uniformly at random.

5 Query $f$ at points $x_{1},\dots,x_{m}$.

6 Query $f$ at point $y=\mathbin{\oplus}_{j\in S}x_{j}$, where $S$ is a
uniformly random subset of $[m]$ of size $\frac{m}{2}$.

7 if  _$\mathcal{O}(y)\cdot\Pi_{j\in S}\mathcal{O}\left(x_{j}\right)=-1$_ then

8 Reject $\triangleright$ This implies no erasures in this iteration.

9

Accept

Algorithm 2 Online-Erasure-Resilient Linearity Tester

Crucially, in each iteration, the distribution over the queries made by
Algorithm 2 is identical to that in the $\text{\sc XorTest}_{k}$ test. Indeed,
as $S$ and $X$ are independent, we could draw $S$ first. Then, for each choice
of $S$, the marginal distribution of ${\left\\{x_{j}\right\\}}_{j\in S}$ is
uniform over $\left({{\left\\{0,1\right\\}}^{n}}\right)^{k}$. Finally, the
last query is $y=\mathbin{\bigoplus}_{j\in S}x_{j}$, resulting in the same
distribution on the $k+1$ queries as in $\text{\sc XorTest}_{k}$.

The second ingredient we need is the following lemma.

######  Lemma 3.2.

For all $m\geq 10$, the probability that one specific iteration of the loop in
Line 2 of Algorithm 2 queries an erased point is at most $3\alpha/25$.

We next restate and prove the main theorem of this section, deferring the
proof of Lemma 3.2 to the next section. See 1.1

###### Proof.

We first focus on erasures, and show that Algorithm 2 satisfies the conditions
of the theorem. Clearly, it always accepts all linear functions. Now, fix an
adversarial (budget-managing) strategy and suppose that the input function is
$\epsilon$-far from linear. By Lemma 3.1 and since $k=m/2$ in Algorithm 2 is
even, the probability that one iteration of the loop in Step 2 samples a
witness of nonlinearity is at least
$\alpha=\min{\left\\{1/4,m\epsilon/4\right\\}}.$

By Lemma 3.2, the probability that an erasure is seen in a specific iteration
is at most $\frac{3\alpha}{25}$. By a union bound, the probability of a single
iteration seeing an erasure or not selecting a witness of nonlinearity is at
most $1-\alpha+\frac{3\alpha}{25}=1-\frac{22\alpha}{25}$. Algorithm 2 errs
only if this occurs in all iterations. By independence of random choices in
different iterations, the failure probability is at most

$\Big{(}1-\frac{22\alpha}{25}\Big{)}^{r}\leq\Big{(}1-\frac{22\alpha}{25}\Big{)}^{\frac{5}{4\alpha}}\leq
e^{-1.1}\leq\frac{1}{3},$

where we used that
$r=\left\lceil{\frac{5}{4\alpha}}\right\rceil\geq\frac{5}{4\alpha}$ and
$1-x\leq e^{-x}$ for all $x$. The query complexity is at most

$r(m+1)\leq\left(\frac{5}{4\alpha}+1\right)(m+1)\leq\frac{4m}{\alpha}=\max{\left\\{16m,\frac{16}{\epsilon}\right\\}}\leq\max{\left\\{640\cdot\log
t,\frac{640}{\epsilon}\right\\}},$

where the last inequality is due to the fact that $m\leq 20(\log
t+1/\epsilon)$.

To show that Algorithm 2 is also corruption-resilient, one may apply [KRV23,
Lemma 1.8], which essentially says an error-resilient algorithm that has
probability at most $1/3$ to either err or see a manipulation, is also
corruption-resilient. For the soundness, our analysis holds since it suffices
to have one iteration that finds a witness without seeing manipulations. For
completeness, note that the algorithm can only err if it has seen a
manipulation, and the probability of seeing a manipulation at any iteration is
at most $3\alpha/25$ by Lemma 3.2. Using a union bound, the overall
probability of seeing any manipulated entry during the entire execution is at
most

$\frac{3\alpha}{25}\cdot
r\leq\frac{3\alpha}{25}\left(\frac{5}{4\alpha}+1\right)=\frac{3}{20}+\frac{3\alpha}{25}\leq\frac{1}{3}.\qed$

######  Remark.

Our tester is applicable for $t\leq\text{poly}(\epsilon)\cdot 2^{n/2}$. On the
other hand, it can be easily shown that for $t=\Omega\left(\epsilon
2^{n}\right)$ testing is impossible. This follows from the fact that there
exists some constant $c$ such that $c/\epsilon$ queries are not enough, and by
then the adversary can already manipulate all other entries. We leave it as an
open question to understand for which values of $t$ linearity can be tested in
the online setting. Such questions are investigated for other properties in
Section 6.

###  3.3 Probability of Seeing an Erasure

Recall that Lemma 3.1 shows that, assuming $f$ is $\epsilon$-far, the
probability of spotting a witness in a single iteration is at least
$\alpha=\min\\{\frac{1}{4},\frac{m\epsilon}{4}\\}$. In this section we prove
the probability of querying an erasure is at most $3\alpha/25$ in every
iteration, as stated in Lemma 3.2. We start with an auxiliary claim, similar
to an argument that appears in the proof of [KRV23, Lemma 2.8].

######  Claim 3.3.

Fix an iteration of the loop in Step 2 of Algorithm 2. For all
$T\subseteq[m]$, let $y_{{}_{T}}=\mathbin{\bigoplus}_{j\in T}x_{j}$. Then, the
probability there exist two subsets $T_{1}\neq T_{2}$ of the set $[m]$ with
$y_{{}_{T_{1}}}=y_{{}_{T_{2}}}$ is small:

${\Pr_{X}\left[{\exists T_{1}\neq T_{2}\text{\rm\ such that\
}y_{{}_{T_{1}}}=y_{{}_{T_{2}}}}\right]}\leq\frac{\alpha}{25}.$

###### Proof.

We first bound $m$ using its setting in Algorithm 2 and the premise
$t\cdot\log^{2}t\leq 2^{-21}\cdot\epsilon^{2.5}2^{n/2}$ from Theorem 1.1:

$\displaystyle
m\leq\log\left(\frac{2^{18}t\log^{2}t}{\epsilon^{2}}\right)\leq\log\left(\frac{2^{-3}\epsilon^{2.5}2^{n/2}}{\epsilon^{2}}\right)\leq\log\left(\sqrt{\epsilon\cdot
2^{n}/50}\right)=\frac{\log\left(\epsilon\cdot 2^{n}/50\right)}{2}.$ (3)

Consider two distinct sets $T_{1},T_{2}\subset[m]$. W.l.o.g. there exists an
element $\ell\in T_{1}\setminus T_{2}$. Fix all entries in $X$ besides
$x_{\ell}$. The value of $y_{{}_{T_{2}}}$ is now fixed, but over the random
choice of $x_{\ell}\in{{\left\\{0,1\right\\}}^{n}}$, the vector
$y_{{}_{T_{1}}}$ is uniform over ${{\left\\{0,1\right\\}}^{n}}$. Thus,
$\Pr_{x_{\ell}}[y_{{}_{T_{1}}}=y_{{}_{T_{2}}}]=2^{-n}$ and, consequently,

$\Pr_{X}[y_{{}_{T_{1}}}=y_{{}_{T_{2}}}]=\mathbb{E}\big{[}\Pr_{x_{\ell}}[y_{{}_{T_{1}}}=y_{{}_{T_{2}}}]\big{]}=\mathbb{E}[2^{-n}]=2^{-n},$

where both expectations are over all entries in $X$ besides $x_{\ell}$, which
are drawn independently from $x_{\ell}$. We use a union bound over all pairs
of subsets $T_{1}$ and $T_{2}$, and then apply (3) to get

${\Pr_{X}\left[{\exists T_{1}\neq T_{2}\text{\rm\ such that\
}y_{{}_{T_{1}}}=y_{{}_{T_{2}}}}\right]}\leq\frac{2^{2m}}{2^{n}}\leq\frac{\epsilon}{50}\leq\frac{\alpha}{25}.$

The last inequality holds since
$\epsilon\leq\min\\{1/2,m\epsilon/2\\}=2\alpha$ for all $m\geq 2$. ∎

We now upper bound the probability of seeing an erasure in one iteration.

###### Proof of Lemma 3.2.

The total number of erasures performed during the execution of the algorithm
is at most $tr(m+1)$. We define three bad events and give upper bounds on
their probabilities.

##### An erasure while querying $X$.

Let $B_{1}$ be the event that $\mathcal{O}(x_{j})=\perp$ for some point
$x_{j}$ sampled in this iteration, where $j\in[m]$. Each point $x_{j}$ is
sampled uniformly from ${{\left\\{0,1\right\\}}^{n}}$, so the probability it
is erased is at most $tr(m+1)/2^{n}$. By a union bound over all $m$ points,
recalling $n\geq 2m$, we get

$\Pr_{X}[B_{1}]\leq\frac{tr(m+1)m}{2^{n}}\leq\frac{tr(m+1)m}{2^{2m}}.$ (4)

#####  $X$ induces a bad distribution of $y$ points.

Let $B_{2}$ be the event that, in this iteration, there exist two different
choices of $S$ leading to the same choice $y\in{{\left\\{0,1\right\\}}^{n}}$.
By Claim 3.3, $\Pr[B_{2}]\leq\frac{\alpha}{25}$.

##### An erasure on query $y$.

Let $B_{3}$ be the event that $\mathcal{O}(y)=\perp$ for $y$ queried in this
iteration. The adversary knows $X$ before $y$ is queried, but there are plenty
of choices for $y$. Conditioned on $\overline{B_{2}}$, the distribution of $y$
is uniform over $\binom{m}{m/2}$ different choices. We use $\binom{m}{m/2}\geq
2^{m}/\sqrt{2m}$, to obtain

$\Pr[B_{3}|\overline{B_{2}}]\leq\frac{tr(m+1)}{\binom{m}{m/2}}\leq\frac{tr(m+1)\sqrt{2m}}{2^{m}}.$
(5)

In terms of the bad events, the lemma states that $\Pr[B_{1}\cup B_{3}]\leq
3\alpha/25.$ By using a union bound over $B_{1}$ and $B_{3}$ and then the law
of total probability to compute $\Pr[B_{3}]$, we get

$\displaystyle\Pr[B_{1}\cup B_{3}]$
$\displaystyle\leq\Pr[B_{1}]+\Pr[B_{3}|\overline{B_{2}}]\cdot\Pr[\overline{B_{2}}]+\Pr[B_{3}|B_{2}]\Pr[B_{2}]\leq\underbrace{\Pr[B_{1}]+\Pr[B_{3}|\overline{B_{2}}]}_{(\star)}+\Pr[B_{2}].$

Since $\Pr[B_{2}]\leq\frac{\alpha}{25}$, it remains to show that
$(\star)\leq\frac{2\alpha}{25}$, in order to complete the proof. To do this,
we combine the bounds from (4) and (5):

$(\star)=\Pr[B_{1}]+\Pr[B_{3}|\overline{B_{2}}]\leq\frac{tr(m+1)m}{2^{2m}}+\frac{tr(m+1)\sqrt{2m}}{2^{m}}\leq\frac{trm^{2}}{2^{m+1}}\leq\frac{rm^{2}\epsilon^{2}}{2^{15}\log^{2}t}.$
(6)

For the second inequality, we use the fact that
$\frac{(m+1)m}{2^{m}}+(m+1)\sqrt{2m}\leq\frac{m^{2}}{2}$ for all $m\geq 10$.
For the last inequality, we use the value of $m$ from Algorithm 2 which
satisfies $2^{m}\leq\frac{2^{14}t\log^{2}t}{\epsilon^{2}}$. To further bound
(6), we split the analysis into two cases, depending on the value of
$\alpha=\min\\{1/4,m\epsilon/4\\}$.

Case I: $\alpha=\frac{m\epsilon}{4}$.  In this case, there are
$r=\left\lceil{\frac{5}{m\epsilon}}\right\rceil\leq\frac{5}{m\epsilon}+1$
iterations, which means that $rm\epsilon\leq 5+m\epsilon\leq 6$. Therefore,

$(\star)\leq\frac{(rm\epsilon)m\epsilon}{2^{15}\log^{2}t}\leq\frac{6m\epsilon}{2^{15}\log^{2}t}\leq\frac{m\epsilon}{50}=\frac{2\alpha}{25}.$

Case II: $\alpha=\frac{1}{4}$.  For this case, note that

$\displaystyle m$ $\displaystyle\leq 18+\log t+2\log\log t+2\log(1/\epsilon)$
$\displaystyle\leq 18+2.1\log t+1.1/\epsilon\leq 11.2\cdot\max\\{2\log
t,1/\epsilon\\},$

where the second inequality uses $2\log y\leq 1.1y$ for all $y>0$ (with
$y=1/\epsilon$ and $y=\log t$), and the last inequality uses $2\log t\geq 2$
and $1/\epsilon\geq 2$. It follows that

$\frac{m\epsilon}{2\log t}\leq 11.2\frac{\max\\{2\log t,1/\epsilon\\}}{2\log
t\cdot 1/\epsilon}=\frac{11.2}{\min\\{2\log t,1/\epsilon\\}}\leq 5.7.$

Finally, we use $r=\left\lceil{\frac{5}{4\alpha}}\right\rceil=5$ to obtain
from Equation 6

$(\star)\leq\frac{r}{2^{13}}\left(\frac{m\epsilon}{2\log
t}\right)^{2}\leq\frac{5\cdot(5.7)^{2}}{2^{13}}\leq\frac{1}{50}=\frac{2\alpha}{25}.\qed$

##  4 The Lower Bound for Low-Degree Testing

In this section, we prove our lower bound for online low-degree testing. See
1.2

###### Proof.

Fix a degree $d>1$. Let $\binom{n}{\leq d}$ denote
$\sum_{i=0}^{d}\binom{n}{i}$. For a vector $x\in\mathbb{F}_{2}^{n}$, define
its extension ${\sf Ext}_{d}(x)\in\mathbb{F}_{2}^{\binom{n}{\leq d}}$ to be
the vector where each entry is indexed by a set $S\subseteq[n]$ of at most $d$
coordinates and ${\sf Ext}_{d}(x)_{S}=\prod_{i\in S}x_{i}$. In other words,
each entry of ${\sf Ext}_{d}(x)$ is an evaluation of one monomial of degree at
most $d$ on input $x$. The extended vector ${\sf Ext}_{d}(x)$ includes all
entries $x_{i}$ of $x$ (as entries indexed by singletons
$S={\left\\{i\right\\}}$). We define projection $\pi$ as the inverse of ${\sf
Ext}_{d}$, i.e., $\pi({\sf Ext}_{d}(x))=x$.

Consider the following strategy ${\cal S}$ for a fixed-rate erasure adversary.
Suppose the tester has successfully obtained answers to $k$ distinct queries
$y_{1},\dots,y_{k}$. Consider the linear space in
$\mathbb{F}_{2}^{\binom{n}{\leq d}}$ spanned by ${\sf
Ext}_{d}(y_{1}),\dots,{\sf Ext}_{d}(y_{k})$, and let
$Z\subseteq\mathbb{F}_{2}^{n}$ denote set of projections of its vectors back
to $\mathbb{F}_{2}^{n}$ using $\pi$. Note that $y_{i}\in Z$ for $i\in[k]$. The
adversary simply tries to erase all (non-erased, non-queried) points of $Z$.
Observe that $Z$ is determined by the queries made by the tester and does not
depend on the input function $f$. We next show that $\left|{Z}\right|$ is
small relative to $k$, and so unless $k$ is large enough, the adversary can
entirely erase $Z$.

######  Claim 4.1.

Let $r=|Z|.$ Then $\binom{\left\lfloor{\log r}\right\rfloor}{d}\leq k$.

###### Proof.

Consider the matrix $A$ with rows indexed by polynomials of degree at most $d$
and columns indexed by vectors $z\in Z$, where the entry indexed by a
polynomial $p$ and a point $z$ contains the value $p(z)\in\mathbb{F}_{2}$. To
prove the claim, we give two bounds on the rank of $A.$

##### Upper bound: $rk(A)\leq k$.

Let $A^{\prime}$ be the submatrix of $A$ with rows indexed by monomials. Since
every degree-$d$ polynomial is a linear combination of monomials, we have
$rk(A)=rk(A^{\prime})$. In $A^{\prime}$, the column indexed by $z$ is exactly
the extended vector ${\sf Ext}_{d}(z)$. By definition, every column in
$A^{\prime}$ is spanned by the $k$ columns indexed by $y_{1},\dots,y_{k}$,
showing that $rk(A^{\prime})\leq k$.

##### Lower bound: $rk(A)\geq\binom{\left\lfloor{\log r}\right\rfloor}{d}$.

Let $B$ be an arbitrary submatrix of $A$ with only $r^{\prime}\leq r$ columns,
where $r^{\prime}=2^{a}$ is the largest power of $2$ not exceeding $r$.
Trivially, $rk(A)\geq rk(B)$. We now apply [BEHL12, Lemma 1.4] (or [KS05,
Theorem 1.5]) to see that the dimension of the rows of $B$ is at least

$\binom{a}{\leq d}\geq\binom{a}{d}=\binom{\left\lfloor{\log
r}\right\rfloor}{d}.$

The two inequalities together yield the claim. ∎

Now we apply Yao’s minimax principle for the online model [KRV23, Corollary
9.4]. It states that to prove a lower bound $q$ on the worst-case query
complexity of online-erasure-resilient property testing, it suffices to give
an adversarial strategy ${\cal S}$, a distribution $\mathcal{D}^{+}$ on
positive instances, and a distribution $\mathcal{D}^{-}$ on instances that are
negative with probability at least $\frac{6}{7}$, such that every
deterministic $q$-query algorithm that accesses its input via an oracle using
strategy ${\cal S}$ sees the same distribution on the the query-answer
histories under ${\cal D}^{+}$ and ${\cal D}^{-}$.

Let ${\cal D}^{+}$ be the uniform distribution over all degree $d$ Boolean
functions on $\\{0,1\\}^{n}$ and ${\cal D}^{-}$ be the uniform distribution
over all Boolean functions on $\\{0,1\\}^{n}$.

We show that a function $f\sim{\cal D}^{-}$ is $\frac{1}{3}$-far from ${\cal
P}_{d}$ (set of functions of degree at most $d$) with probability at least
$6/7$. Let $g\in{\cal P}_{d},f\sim{\cal D}^{-},$ and ${\text{dist}}(f,g)$ be
the fraction of domain points on which $f$ and $g$ differ. Then,
$\mathbb{E}[dist(f,g)]=1/2$. By the Hoeffding bound, $\Pr_{f\sim{\cal
D}^{-}}[{\text{dist}}(f,g)\leq\frac{1}{3}]\leq e^{-\frac{2^{n}}{18}}$. By a
union bound over the $2^{\binom{n}{\leq d}}$ functions of degree at most $d$,
we get $\Pr_{f\sim{\cal D}^{-}}[dist(f,{\cal P}_{d})\geq\frac{1}{3}]\geq
1-2^{\binom{n}{\leq d}}\cdot e^{-\frac{2^{n}}{18}}$. For large enough $n$,
this probability is at least $6/7$.

Let $A$ be a deterministic algorithm that makes $q\leq\binom{\left\lfloor{\log
t}\right\rfloor-1}{d}$ queries to the oracle ${\cal O}$ with adversarial
strategy ${\cal S}$. By 4.1, we get $r\leq t$, i.e., after each query $y_{i}$
for $i\in[q]$, the adversary has sufficient erasure budget to erase $Z$. We
argue that the distributions on the histories of query answers are the same
under the distributions ${\cal D}^{+}$ and ${\cal D}^{-}$. Under both
distributions, the adversary erases the same query points. Consider a query
$y_{k}$ of $A$ that is not erased and suppose it is made after $A$
successfully obtained answers $a_{1},\dots,a_{k-1}$ to distinct queries
$y_{1},\dots,y_{k-1}$. When $f\sim{\cal D}^{-}$, we have $\Pr_{f\sim{\cal
D}^{-}}[f(y_{k})=a_{k}\mid f(y_{1})=a_{1}\wedge\dots\wedge
f(y_{k-1})=a_{k-1}]=1/2$ for all $a_{1},\dots,a_{k}\in\\{0,1\\}$, since the
value of $f(y_{k})$ is set uniformly and independently of values at other
points. Now consider $f\sim{\cal D}^{+}$, viewed as a uniformly random
coefficient vector ${\mathds{1}}_{f}\in{\left\\{0,1\right\\}}^{\binom{n}{\leq
d}}$, where each entry corresponds to a monomial of degree at most $d$. For
any query it holds that $f(y_{i})=\left\langle{{\mathds{1}}_{f}},{{\sf
Ext}_{d}(y_{i})}\right\rangle$. By definition of ${\cal S}$, the extension
${\sf Ext}_{d}(y_{k})$ is linearly independent of ${\sf
Ext}_{d}(y_{1}),\dots,{\sf Ext}_{d}(y_{k-1})$, which implies that for any
fixed values $b_{1},\dots b_{k-1}$ of $\left\langle{{\mathds{1}}_{f}},{{\sf
Ext}_{d}(y_{i})}\right\rangle,\dots,\left\langle{{\mathds{1}}_{f}},{{\sf
Ext}_{d}(y_{k-1})}\right\rangle$, the value of
$\left\langle{{\mathds{1}}_{f}},{{\sf Ext}_{d}(y_{k})}\right\rangle$ is still
uniformly distributed.

Thus, ${\cal D}^{+}$ generates degree-$d$ polynomials, ${\cal D}^{-}$
generates functions that are $\frac{1}{3}$-far from ${\cal P}_{d}$ with
probability at least $\frac{6}{7}$, and the query-answer histories for any
deterministic algorithm $A$ that makes $q\leq\binom{\left\lfloor{\log
t}\right\rfloor-1}{d}$ queries and runs against the $t$-online fixed-rate
erasure oracle employing strategy ${\cal S}$ are identical under ${\cal
D}^{+}$ and ${\cal D}^{-}$. Consequently, Yao’s principle implies the desired
lower bound. ∎

##  5 Low-Degree Testing

This section is dedicated to the proof of Theorem 1.3 that gives an online
tester for the property ${\cal P}_{d}$ (being a polynomial of degree at most
$d$) with batches of size $b=2^{d-1}.$

Our strategy is a natural extension of the one employed for linearity in
Section 3.2: we view the $\text{\sc XorTest}_{2}$ as a “linear square”
($x,y,x+y$, omitting the origin), and perceive the extended test as a “chain
of squares” (see the top part of Figure 1). For quadraticity and any degree
$d>2$, we resort to “chains of cubes” in a similar way (see the bottom part of
Figure 1).

Figure 1: Chains of cubes (with 0 as the first parameter). The left side shows
linear subspaces (drawn as cubes); the right side shows chains formed by two
cubes. Red points overlap and cancel each other. From top to bottom, we have
witnesses for linearity (chains of squares), witnesses for quadraticity (each
vertical edge represents a batch of $b=2$ points), and witnesses for ${\cal
P}_{d}$, where each batch queries an affine subspace with a fixed linear
component $A$ and different translations.

###  5.1 Algebraic Testing Patterns

In the following, we define a _testing pattern_ to be a mapping from a set of
parameters to a structured set of points (e.g., mapping parameters $x,y$ to
the three points $x,y,x+y$). Setting a value to all parameters induces an
_instance_ of the testing pattern. To test for a low-degree property ${\cal
P}_{d}$, we simply draw a random instance of some “good” pattern and check the
parity of the sum of function values on the points in the pattern. This is a
generalization of the tester of [AKK+05], which checks the parity on a random
linear subspace (which is an example of a good testing pattern).

Our notion of a good testing pattern is a special case of the more abstract
notion of _$k$ -local formal characterizations_ (see [KS08, Definition 2.3]),
where each linear map defines a single testing point, and the subspace $V$ of
“good vectors” is fixed to all answer vectors with parity $0$. In particular,
a good testing pattern is a $2$-ary independent characterization (see [KS08,
Definition 2.5]).

######  Definition 5.1 (Testing pattern, parameter, instance).

A _testing pattern_ is a matrix555We use $\mathcal{M}_{\ell\times
m}(\mathbb{F}_{2})$ for the set of $\ell\times m$ matrices with entries in
$\mathbb{F}_{2}.$

$X\in\mathcal{M}_{\ell\times m}(\mathbb{F}_{2})$

with rows $c_{1},\dots,c_{\ell}$, such that $\ell\geq m$, each row is unique,
and $rank(X)=m$. An _instance_ of a pattern $X$ is described by the product
$XM\in\mathcal{M}_{\ell\times n}(\mathbb{F}_{2})$, for some parameter matrix
$M\in\mathcal{M}_{m\times n}(\mathbb{F}_{2})$. The rows of $XM$ specify $\ell$
testing points $y_{1},\dots,y_{\ell}$ in $\mathbb{F}_{2}^{n}$.

Generalizing the notation from [AKK+05], for a function $f$ and a pattern
instance $XM$, we denote the sum (over $\mathbb{F}_{2}$) of the values of $f$
on these points by

$T_{X,f}(a_{1},\dots,a_{m}):=\sum_{i\in[\ell]}f(y_{i}).$

Each testing pattern induces a parity-checking tester, defined below.

Input : a pattern $X\in\mathcal{M}_{\ell\times m}(\mathbb{F}_{2})$ and query
access to a function $f:\mathbb{F}_{2}^{n}\to\mathbb{F}_{2}$

1 Choose a parameter matrix $M\in\mathcal{M}_{m\times n}(\mathbb{F}_{2})$
uniformly at random (alternatively, choose $m$ row vectors
$a_{1},\dots,a_{m}\in\mathbb{F}_{2}^{n}$ independently and uniformly at
random).

2 Query $f$ at testing points $y_{1},\dots,y_{\ell}$, the $\ell$ row vectors
of the instance matrix $XM$.

Accept if $T_{X,f}(a_{1},\dots,a_{m})=0$; otherwise, reject.

Algorithm 3 An $X$-tester

Next, we define a good testing pattern to have two desired properties.

######  Definition 5.2 (Good patterns).

A pattern $X_{\ell\times m}$ is _complete_ for a property $\mathcal{P}$ if for
all functions $f\in\mathcal{P}$,

${\Pr_{a_{1},\dots,a_{m}}\left[{T_{X,f}(a_{1},\dots,a_{m})=1}\right]}=0.$

A pattern $X_{\ell\times m}$ is _minimally sound_ for a property $\mathcal{P}$
if for all functions $f\notin\mathcal{P}$,

${\Pr_{a_{1},\dots,a_{m}}\left[{T_{X,f}(a_{1},\dots,a_{m})=1}\right]}>0.$

If a pattern is both complete and minimally sound for ${\cal P}$, we call it
_good_ for ${\cal P}$.

In other words, a good pattern $X_{\ell\times m}$ for a property ${\cal P}$
characterizes ${\cal P}$:

$f\in\mathcal{P}\ \iff\ \forall a_{1},\dots,a_{m}:\
T_{X,f}(a_{1},\dots,a_{m})=0.$

In the context of testing $f\in{\cal P}_{d}$, we have the following useful
characterization of good patterns.

######  Claim 5.3.

A pattern $X\in\mathcal{M}_{\ell\times m}(\mathbb{F}_{2})$ is good for ${\cal
P}_{d}$ if and only if the two conditions hold:

  1. (i)

For all coordinate sets $S\subseteq[m]$ of size $\left|{S}\right|\leq d$, we
have $\ \displaystyle\sum_{i\in[\ell]}\prod_{j\in S}X_{ij}=0.$

  2. (ii)

There exists a set $S\subseteq[m]$ of size $\left|{S}\right|=d+1$ such that $\
\displaystyle\sum_{i\in[\ell]}\prod_{j\in S}X_{ij}=1.$

The proof of this claim is deferred to Appendix B, it generalizes the one of
[AKK+05, Lemma 1].

###  5.2 Generalized Witnesses for ${\cal P}_{d}$

The tester of [AKK+05], discussed in Section 1.1.2, queries a linear
$(d+1)$-dimensional subspace; the variant of the tester considered in [BKS+10]
uses an affine $(d+1)$-dimensional subspace. Both subspaces can be represented
as cubes666We call them cubes for easy visualisation, even though most pattern
instances are not parallel to the axes.. The affine version of the tester is
equivalent to $X$-tester with the pattern $X$ with $d+1$ parameters
$a_{1},\dots,a_{d+1}$ representing directions and a translation parameter
$a_{d+2}$. The rows of pattern $X$ are all different binary vectors of $d+2$
bits with value $1$ at the last coordinate. It is easy to verify this pattern
satisfies the conditions of 5.3. (For the tester based on a linear subspace
simply delete the last column of $X$, which corresponds to fixing the last
parameter $a_{d+2}=\vec{0}$.) For the special case of affinity ($d=1)$, this
pattern can be equivalently viewed as taking parameters $x_{1},x_{2},x_{3}$ to
testing points ${\left\\{x_{1},x_{2},x_{3},x_{1}+x_{2}+x_{3}\right\\}}$ (the
BLR linearity test simply fixes $x_{3}=0$), and the generalized witness used
in Algorithm 1 can be viewed as a “chain of squares”: the second square shares
the point $x_{1}+x_{2}+x_{3}$ as if it was its first parameter, and gets
additional parameters $x_{4},x_{5}$. When we check the parity of $f$ on all
points in both squares, the intermediate point $x_{1}+x_{2}+x_{3}$ appears
twice and cancels out. We are left with testing points $x_{1},\dots,x_{5}$ and
their sum $\sum_{i\in[5]}x_{i}$.

To generalize this to higher dimensions, we consider the similar picture for
high-dimensional cubes. Alternatively, we can view this as the chain from
linearity, but each point is replaced with an entire $(d-1)$-dimensional cube
(see fig. 1). Note the parameters of these patterns have two different roles,
some parameters impose the chain structure while others are used for the
cubical structure. We dub these patterns “chains of cubes”.

######  Definition 5.4 (Chain of Cubes Pattern).

For degree $d$ and odd integer $s$ (length of the chain), we define the chain
of cubes pattern $\chi_{d,s}$. It takes parameters $a_{1},\dots,a_{d}$ for the
cube structure, and $a_{d+1},\dots,a_{d+s}$ for the chain, and outputs
$(s+1)\cdot 2^{d-1}$ testing points, each is a combination of a subset of the
first $d$ parameters, and either all or exactly one of the last $s$
parameters.

Formally, $\chi_{d,s}$ has “cube columns” $1,\dots,d$ and “chain columns”
$d+1,\dots,d+s$. We index each row with
$i\in[s+1],j\in{{\left\\{0,1\right\\}}^{d}}$. In row $(i,j)$, the first $d$
coordinates are exactly the vector $j$. The last $s$ coordinates depend on
$i$, where if $i\in[s]$ then only column $d+i$ has value $1$, and if $i=s+1$
then all $s$ columns have value $1$.

######  Claim 5.5.

The chain of cubes pattern $\chi_{d,s}$ is good for ${\cal P}_{d+1}$ for all
$d\in\mathbb{N}$ and all odd $s$.

###### Proof.

We show the pattern $\chi_{d,s}$ satisfies the conditions of 5.3. That is,
each set of at most $d+1$ coordinates has an even number of rows where all
these coordinates are $1$, and there exists a set of $d+2$ coordinates for
which the number of such rows is odd.

Let $T$ be a set of $d+1$ coordinates. Then $T$ includes at least one chain
coordinate, as there are only $d$ cube coordinates. First, suppose that $T$
includes exactly one chain coordinate $c\in{\left\\{d+1,\dots,d+s\right\\}}$.
Rows where all coordinates in $T\setminus{\left\\{c\right\\}}$ are $1$ come in
pairs, indexed either $(c,j)$ or $(s+1,j)$ for any fitting $j$. Thus, there is
an even number of them. Next, suppose $T$ includes at least two coordinates
from ${\left\\{d+1,\dots,d+s\right\\}}$. Then, there exists a cube column
$c\in[d]$ such that $c\notin T$. For each row where all coordinates in $T$ are
$1$, coordinate $c$ can be 0 or 1, leading to an even number of such rows.

To show the pattern is minimally sound, consider the set $T=[d+2]$. Two chain
coordinates together are $1$ only in rows indexed by $(s+1,j)$ for some $j$.
But $j$ must be $\vec{1}$ to get $1$ in all the first $d$ coordinates. Thus,
only a single row has value $1$ on all coordinates in $T$. ∎

###  5.3 Soundness of Patterns

In this section, we show a soundness result for any pattern, and in particular
for our chain of cubes pattern, $\chi_{d,s}$. We resort to two previously
known results and combine them together. The first is inherited by the
soundness guarantee in [KS08] for any $2$-ary local characterization.

The other is a specialized argument for affine subsapces that appears in
[BKS+10]. The argument deals with small values of $\epsilon$ (so most
violating instances are such due to a single point). We generalize this
argument for any pattern, relying on two properties held by all patterns.
First, each two induced testing points, over a random instance, are
independent. Second, the tester depends on the parity of all answers to the
queried points.

Formally, we prove the following lemma.

######  Lemma 5.6.

Fix any pattern $X\in\mathcal{M}_{\ell\times m}(\mathbb{F}_{2})$ with
$\ell\geq 3$. For any function $f$ that is $\epsilon$-far from ${\cal P}_{d}$,
we have

${\Pr_{a_{1},\dots,a_{m}}\left[{T_{X,f}(a_{1},\dots,a_{m})=1}\right]}\geq\min{\left\\{\frac{\ell\epsilon}{2},\frac{1}{2\ell^{2}}\right\\}}.$

###### Proof.

Our starting point is the soundness guarantee of local characterization, that
is Theorem 2.9 in [KS08]. Any pattern $X\in\mathcal{M}_{\ell\times
m}(\mathbb{F}_{2})$ is a $2$-ary $\ell$-local characterization, where each row
dictates a function, and a vector in ${{\left\\{0,1\right\\}}^{\ell}}$ of
evaluations of $f$ is rejected if and only if its hamming weight is odd.
Moreover, the first row is linearly independent from all the others (since
each two rows are distinct and we are over $\mathbb{F}_{2}$). Thus, for any
$\epsilon$-far function $f$, we get:

${\Pr_{a_{1},\dots,a_{m}}\left[{T_{X,f}(a_{1},\dots,a_{m})=1}\right]}\geq\min{\left\\{\epsilon/2,\gamma(\ell)\right\\}},$
(7)

where $\gamma(\ell)=1/((2\ell+1)(\ell-1))$ only depends on $\ell$.

Next, we adjust the argument from Lemma 8 in [BKS+10]. Let $g$ be a degree-$d$
function that achieves minimal distance, $\epsilon$, from $f$. Our probability
space is the random choice of parameters $a_{1},\dots a_{m}$. We observe two
types of events for each $i\in[\ell]$. The first event is $E_{i}$ \- the event
that $f(y_{i})\neq g(y_{i})$. The second is $F_{i}$ \- the event that
$f(y_{i})\neq g(y_{i})$ but $f(y_{j})=g(y_{j})$ for all $j\neq i$.

Since each $y_{i}$ is uniform over $\mathbb{F}_{2}^{n}$, it is clear that
${\Pr\left[{E_{i}}\right]}=\epsilon$. Due to the fact that each two rows are
different (and hence, over $\mathbb{F}_{2}$, linearly independent), we get
pairwise independence for the variables $y_{1},\dots,y_{\ell}$. I.e, for any
$i\neq j$ we have ${\Pr\left[{E_{i}\wedge E_{j}}\right]}=\epsilon^{2}$. It is
clear that for all $i\in[\ell]$:

${\Pr\left[{F_{i}}\right]}\geq{\Pr\left[{E_{i}}\right]}-\sum_{j\neq
i}{\Pr\left[{E_{i}\wedge E_{j}}\right]}\geq\epsilon-\ell\epsilon^{2}.$

Note that $g\in{\cal P}_{d}$ passes the parity-check for every instance,
meaning that for $f$ it depends on the number of points in the instance in
which it differs from $g$. In particular, the test rejects if $f$ differs from
$g$ on _exactly one_ such point. This event is exactly the disjoint union of
all events $F_{i}$, and its probability is lower bounded by

${\Pr\left[{\bigsqcup_{i\in[\ell]}F_{i}}\right]}=\sum_{i\in[\ell]}{\Pr\left[{F_{i}}\right]}\geq\ell\left(\epsilon-\ell\epsilon^{2}\right)=\ell\epsilon(1-\ell\epsilon).$

Thus, for any $\epsilon$-far function $f$, we get

${\Pr_{a_{1},\dots,a_{m}}\left[{T_{X,f}(a_{1},\dots,a_{m})=1}\right]}\geq\ell\epsilon(1-\ell\epsilon).$

We finish up by combining both arguments. If $\ell\epsilon\leq 1/2$, we are
guaranteed soundness of at least
$\ell\epsilon(1-\ell\epsilon)\geq\ell\epsilon/2$. Otherwise,
$\ell\epsilon>1/2\geq 1/\ell$, which implies $\epsilon/2>1/(2\ell^{2})$.
Combined with $\gamma(\ell)\geq 1/(2\ell^{2})$, the soundness guaranteed by
Equation 7 must be at least $1/(2\ell^{2})$. ∎

###  5.4 Algorithm with Batches of $2^{d-1}$ Queries

Our low-degree tester is based on multiple simulations of the parity-check
tester with the pattern $\chi_{d-1,m}$, but each simulation uses additional
queries to overcome the adversary, mirroring the simulation of $\text{\sc
XorTest}_{k}$ in Algorithm 2. The number of iterations and the length of the
chain, $m$, are chosen according to the soundness guarantee of these
generalized patterns777Improving the soundness guarantee in Lemma 5.6 to
$\Theta\left(\min{\left\\{\ell\epsilon,1\right\\}}\right)$ would allow a
better choice $m,r$, similar to Algorithm 4, and result in a better query
complexity..

Input : Parameters $\epsilon\in(0,1/2]$ and $d,t\in\mathbb{N}$; query access
to $f$ via $t$-online erasure oracle sequence $\mathcal{O}$ with batch size
$2^{d-1}$

1 $t\leftarrow\max\\{t,2\\}$ $\triangleright$ If $t<2$, replace it with $t=2.$

2 $m\leftarrow 2\left\lceil{\log\left(\frac{2^{20}2^{d}t^{1/4}(d\log
t)^{3/2}}{\epsilon^{1/2}}\right)}\right\rceil+1$,
$\alpha\leftarrow\min{\left\\{\frac{\epsilon\ell}{2},\frac{1}{2\ell^{2}}\right\\}},r\leftarrow\left\lceil{\frac{2}{\alpha}}\right\rceil$.

3 repeat  _$r$_ times

4 Sample $V=(v_{1},\dots,v_{d-1})\in({{\left\\{0,1\right\\}}^{n}})^{d-1}$
uniformly at random.

5 Sample $X=(x_{1},\dots,x_{2m})\in({{\left\\{0,1\right\\}}^{n}})^{2m}$
uniformly at random.

6 for each $i\in[2m]$: batch query $f$ at points $x_{i}+\sum_{j\in T}v_{j}$
for all $T\subseteq[d-1]$.

7 Sample uniformly at random a subset of $[2m]$ of size $m$, denoted
$S={\left\\{s_{1},\dots,s_{m}\right\\}}$.

8 Set $y=\mathbin{\oplus}_{j\in S}x_{j}$ and batch query $f$ at points
$y+\sum_{j\in T}v_{j}$ for all $T\subseteq[d-1]$.

9 if
_$T_{\chi_{d-1,m},\mathcal{O}}(v_{1},\dots,v_{d-1},x_{s_{1}},\dots,x_{s_{m}})=1$_
then

10 Reject $\triangleright$ This implies no erasures in this iteration.

11

Accept

Algorithm 4 Online-Erasure-Resilient Degree-$d$ Tester

###  5.5 Probability of Seeing an Erasure

To analyze the probability of seeing an erasure, we use the structured
(“cube”) part of our patterns, which is evident in our tester as well. This is
done, in essence, by considering the subspace
$A=sp{\left\\{v_{1},\dots,v_{d-1}\right\\}}$ and observing the quotient group
$\mathbb{F}_{2}^{n}/A$, where each element has the form $x+A$ (corresponding
to $2^{d-1}$ points in $\mathbb{F}_{2}^{n}$). Projecting all our queries and
erasures to this group brings us back to the linearity tester.

More formally, assume $dim(A)=d-1$ (if it is smaller, the argument only
improves), and let $U=(u_{d},\dots,u_{n})$ complete the set of vectors $V$ to
a basis of the entire space. Define
$B=sp{\left\\{u_{d},\dots,u_{n}\right\\}}$, and let $\pi_{B}$ be a projections
of any vector $x\in\mathbb{F}_{2}^{n}$ to $B$ using its unique representation
over the basis $V\cup U$. The image of the projection is $B$, which is
isomorphic to $\mathbb{F}_{2}^{n-d+1}$, and for each $u\in B$, its pre-image
is exactly $\pi_{B}^{-1}(u)=u+A={\left\\{u+v\ :\ v\in A\right\\}}$.

We can therefore recast a single iteration of Algorithm 4 in terms of $B$
alone. Projection of a uniformly random point $x_{i}\in\mathbb{F}_{2}^{n}$ is
a uniformly random point $u_{i}\in B$, with $x_{i}+A=u_{i}+A$ (which defines
the same batch of queries). Furthermore, after choosing the random subset of
indices $S$, we get

$\pi_{B}(y)=\pi_{B}\left(\mathbin{\oplus}_{j\in
S}x_{j}\right)=\mathbin{\oplus}_{j\in S}\pi_{B}(x_{j})\in B,$

for which we again query $y+A=\pi_{B}(y)+A$. It is now clear that an iteration
of Algorithm 4 reduced to its queries on $B$ is equivalent to an iteration of
Algorithm 2 on an entire space of dimension $n^{\prime}=n-d+1$ (which $B$ is
isomorphic to). Lastly, we strengthen our adversary, by saying each time it
tries to erase a point $x\in\mathbb{F}_{2}^{n}$, the entire set $x+A$ is
erased instead, and we think of it as an erasure of $\pi_{B}(x)$ in $B$. Thus,
the probability of seeing an erasure, even with the strengthened adversary, is
that of Algorithm 2 seeing an erasure.

Applying the same arguments as in 3.3, with $n^{\prime}=n-d+1$, the adjusted
number of batches, $2m$, and adjusted premise on $t$ leads to the following
claim.

######  Claim 5.7.

Fix an iteration of the loop in Step 4 of Algorithm 4, and denote
$u_{i}=\pi_{B}(x_{i})$. For all $T\subseteq[2m]$, let
$y_{{}_{T}}=\mathbin{\bigoplus}_{j\in T}u_{j}$. Then, the probability there
exist two subsets $T_{1}\neq T_{2}$ of the set $[2m]$ with
$y_{{}_{T_{1}}}=y_{{}_{T_{2}}}$ is small:

${\Pr_{X}\left[{\exists T_{1}\neq T_{2}\text{\rm\ such that\
}y_{{}_{T_{1}}}=y_{{}_{T_{2}}}}\right]}\leq\frac{2^{4m}}{2^{n^{\prime}}}\leq\frac{\epsilon}{2^{20}2^{2d}(d\log
t)^{2}},$

as long as $t\log^{7}t\leq c\cdot\epsilon^{2.5}d^{-7}2^{(n-11d)/2}$ for some
constant $c$.

Finally, we can obtain the following lemma. We omit its proof which is
identical to the proof of Lemma 3.2, using $n^{\prime}\geq 4m$ (instead of
$n\geq 2m$ there).

######  Lemma 5.8.

For all $m\geq 5$, and $t$ as above, the probability that one specific
iteration of the loop in Line 4 of Algorithm 4 queries an erased point is at
most

$\frac{4trm^{2}}{2^{2m+1}}+\frac{\epsilon}{2^{20}2^{2d}(d\log t)^{2}}.$

###  5.6 Analysis of the Online Tester

Now we complete the analysis of Algorithm 4 and prove Theorem 1.3 for erasure
adversaries. Similar to the case of linearity, our tester has a small constant
probability of ever seeing a manipulated entry, and hence it is robust against
corruptions as well. See 1.3

###### Proof for the case of erasures.

We show that Algorithm 4 satisfies the conditions of the theorem. It always
accepts all degree-$d$ functions. Now, fix an adversarial (budget-managing)
strategy and suppose that the input function is $\epsilon$-far from any degree
$d$ function.

By Lemma 5.6 with $\ell=(m+1)2^{d-1}$ points in the $\chi_{d-1,m}$ pattern,
the probability that one iteration the loop in Step 4 samples a witness for
not being degree $d$ is
$\alpha=\min{\left\\{\frac{\ell\epsilon}{2},\frac{1}{2\ell^{2}}\right\\}}.$ We
split the analysis into two cases, depending on which term achieves the
minimum.

Case I: $\alpha=\ell\epsilon/2$, the number of iterations is
$r=\left\lceil{\frac{2}{\alpha}}\right\rceil=\left\lceil{\frac{4}{\ell\epsilon}}\right\rceil$
which means that
$r\ell\epsilon\leq\left(\frac{4}{\ell\epsilon}+1\right)\ell\epsilon=4+\ell\epsilon\leq
5$. By Lemma 5.8, the probability that an erasure is seen within a single
iteration is at most

$\displaystyle\frac{4trm^{2}}{2^{2m+1}}+\frac{\epsilon}{2^{20}2^{2d}(d\log
t)^{2}}.$

We bound the second term naively by $\frac{\epsilon}{100}$. For the first
term, we use the setting of $m$ in the algorithm which implies
$2^{2m}\geq\frac{2^{20}t}{\epsilon^{2}}$, and the fact that $m\leq\ell$ to get

$\frac{4rm^{2}\epsilon^{2}}{2^{20}}\leq\frac{4(rm\epsilon)m\epsilon}{2^{20}}\leq\frac{20m\epsilon}{2^{20}}\leq\frac{m\epsilon}{2^{15}}.$

The probability that an erasure is seen in a specific iteration is therefore
at most

$\displaystyle\frac{m\epsilon}{2^{15}}+\frac{\epsilon}{100}<\frac{\ell\epsilon}{80}.$

By a union bound, the probability of a single iteration seeing an erasure or
not selecting a witness is at most
$1-\frac{\ell\epsilon}{2}+\frac{\ell\epsilon}{80}\leq
1-\frac{\ell\epsilon}{3}$. Algorithm 4 errs only if this occurs in all
iterations. By independence of random choices in different iterations, the
failure probability is at most

$\Big{(}1-\frac{\ell\epsilon}{3}\Big{)}^{r}\leq\Big{(}1-\frac{\ell\epsilon}{3}\Big{)}^{\frac{4}{\ell\epsilon}}\leq
e^{-\frac{4}{3}}\leq\frac{1}{3},$

where we used $1-x\leq e^{-x}$ for all $x$.
The total number of queries used in this case is at most $r(2m+1)b\leq
2r\ell\leq 10/\epsilon$.

Case II: $\alpha=\frac{1}{2\ell^{2}}$, and $r=4\ell^{2}$. We first bound $m$,
set in Algorithm 4, in terms of $d$ and $\log t$.

$\displaystyle m$ $\displaystyle\leq 41+2d+\log t+3\log d+3\log\log
t+\log(1/\epsilon)$ $\displaystyle\leq 41+4\log t+8d+3\log m$
$\displaystyle\leq 20(\log t+d)+3\log m,$

The second inequality follows from the fact that, in this case,
$\log(1/\epsilon)\leq 3\log\ell\leq 3(\log m+d)$. Since $m\geq 2^{5}$ we have
$3\log m\leq m/2$ which implies (for $t,d\geq 2$)

$m\leq 40(\log t+d)\leq 2^{6}d\log t.$

To bound the probability that an erasure is seen in one iteration, we start,
like in Case I, with Lemma 5.8. We bound the first term recalling that
$r=4\ell^{2}\leq 4m^{2}2^{2d}$,

$\frac{4trm^{2}}{2^{2m+1}}\leq\frac{8tm^{4}2^{2d}}{2^{2m}}\leq\frac{2^{3}\cdot
2^{2d}m^{4}\epsilon^{2}}{2^{80}2^{4d}(d\log
t)^{6}}\leq\frac{1}{2^{40}m^{2}2^{2d}}\leq\frac{1}{20\ell^{2}},$

where the second inequality plugs in the value of $m$ set in the algorithm to
bound $t/2^{2m}$, and the third uses $m\leq 40d\log t$ in the denominator.
Adding the second term, we get at most

$\frac{4trm^{2}}{2^{2m+1}}+\frac{\epsilon}{2^{20}2^{2d}(d\log
t)^{2}}\leq\frac{1}{20\ell^{2}}+\frac{1}{20\ell^{2}}\leq\frac{1}{10\ell^{2}}.$

By a union bound, the probability of a single iteration seeing an erasure or
not selecting a witness is at most
$1-\frac{1}{2\ell^{2}}+\frac{1}{10\ell^{2}}\leq 1-\frac{1}{3\ell^{2}}$. As
before, we use the independence of different iterations to conclude the
algorithm errs with probability at most
$\big{(}1-\frac{1}{3\ell^{2}}\big{)}^{4\ell^{2}}\leq\frac{1}{3}.$
The total number of queries used is $r(2m+1)b\leq 6m^{3}2^{3d}\leq 240\cdot
2^{3d}(d+\log t)^{3}$. ∎

##  6 Online Erasure-Resilient Testing of Local Sequential Properties

In this section, we establish our results on testing local properties of
sequences discussed in Section 1.1.3. That is, we prove the following two main
results. See 1.4 See 1.5

Our core technical result in this section shows that a simple pair tester
(presented in Algorithm 5) can test all local properties of sequences.

For the algorithm, for $d,n\in\mathbb{N}$, where $d<n$, we define the set of
all distance-$d$ pairs in $[n]$ by888Note that the definition is cyclic, in
the sense that allows for pairs where $x$ is close to $n$, and $y$ is much
smaller and close to $1$. The cyclic nature of the definition slightly
simplifies the algorithm and analysis.

$D_{d}(n)=\\{(x,y)\in[n]^{2}:y-x\equiv d\ (\text{mod}\ n)\\}.$

We also define the _interval_ $[a:b]$ as the set of all integers
$\\{i\in\mathbb{Z}:a\leq i\leq b\\}$. The _length_ of the interval $[a:b]$ is
$b-a+1$. Our algorithm relies on a fundamental notion of _unrepairability_ in
a sequence $f$ with respect to a property $\mathcal{P}$. The notion we use is
a slightly generalized version of a notion of unrepairability for intervals
originally proposed in [Ben19].

######  Definition 6.1 (Unrepairability).

Let $\mathcal{P}$ be a local property of sequences $f\colon[n]\to\mathbb{R}$
characterized by the forbidden family $\mathcal{F}$. For a subset
$S\subseteq[n]$, a sequence $f$ is _unrepairable_ on $S$ with respect to
$\mathcal{P}$ if the following holds: every sequence
$f^{\prime}\colon[n]\to\mathbb{R}$, where $f^{\prime}(x)=f(x)$ for all $x\in
S$, does not satisfy $\mathcal{P}$. (I.e., every $f^{\prime}$ that agrees with
$f$ on all entries in $S$ contains a pattern from $\mathcal{F}$.)

Crucially, given $\mathcal{P}$ and query access to $f$, in order to know
whether $f$ is unrepairable on $S$ w.r.t.$~{}\mathcal{P}$, one needs to query
$f$ only on the elements of $S$. For our purposes, $|S|\leq 2$ always holds,
and so we only need to make two queries in order to check unrepairability.

Note that, up to some edge cases, an interval which satisfies the notion of
unrepairability from [Ben19] is called a _witness interval_ in this paper (see
Definition 6.12 below); the notion of a witness interval is used in the
analysis, but not in the algorithm.

Input : local property $\mathcal{P}$, $\epsilon\in(0,1)$; query access to
$f:[n]\to\mathbb{R}$ (in offline model)

or, for $t\in\mathbb{R}$ and $b\in\mathbb{N}$, via $t$-online erasure oracle
sequence $\mathcal{O}$ with batch size $b$

1 Set $\ell=\lfloor\log\left(\frac{\epsilon n}{4}\right)\rfloor$.

2 repeat  _$\frac{200\log(\epsilon n)}{\epsilon}$_ times

3 Sample $i\in[0:\ell]$ uniformly at random,

4 Sample $(x,y)\in D_{2^{i}}(n)$ uniformly at random; query $f(x)$ and $f(y)$.

5 if  _$f$ is unrepairable on $\\{x,y\\}$ _ then

6 Reject

7

Accept

Algorithm 5 Pair tester for local properties

We first show that the pair tester works for every local property
$\mathcal{P}$ in the _offline_ property testing model. The statement is given
in the following lemma and proved in Section 6.2.

######  Lemma 6.2 (Offline correctness of pair tester).

Algorithm 5 is a nonadaptive $\epsilon$-tester with one-sided error
probability bounded by $1/7$ for every local property $\mathcal{P}$ in the
offline testing model (without erasures or corruptions).

The pair tester not only works in the offline setting, but it is also unlikely
to see erasures in the online setting when $t$ is appropriately small. The
next two lemmas state results of this type for batch sizes 1 and 2,
respectively.

######  Lemma 6.3 (Pair tester, batch size 1).

Fix a local property $\mathcal{P}$, $\epsilon>0$, $n\in\mathbb{N}$, and
$t\leq\epsilon/10^{6}$. The probability that Algorithm 5, when run in the
online erasure model with parameters $\mathcal{P},\epsilon,n,t$ and batch size
$b=1$, queries an erased element is at most $1/7$.

######  Lemma 6.4 (Pair tester, batch size 2).

Fix a local property $\mathcal{P}$, $\epsilon>0$, $n\in\mathbb{N}$, and
$t\leq\frac{\epsilon^{2}n}{3\cdot 10^{5}\log^{2}(\epsilon n)}$. The
probability that Algorithm 5, when run in the online erasure model with
parameters $\mathcal{P},\epsilon,n,t$ and batch size $b=2$, queries an erased
element is at most $1/7$.

Note the sharp contrast between the threshold rate for $b=1$
($t=\Theta(\epsilon)$) and $b=2$ ($t=\tilde{\Theta}(n)$).

The positive results of Theorems 1.4 and 1.5 follow from Lemmas 6.2, 6.3, 6.4.
The proof of the negative (impossibility) result of Theorem 1.4 is given in
Section 6.3.

###### Proof of Theorem 1.4, Part 1.

For an erasure adversary, we use Lemmas 6.2 and 6.3. Consider a local property
${\cal P}$ and a sequence $f$ that is $\epsilon$-far from ${\cal P}$. Let $A$
be the event that the tester rejects, given query access to $f$ (not to the
erasure oracle). Let $B$ be the event that the tester encounters at least one
erasure. The rejection probability of the tester in the online setting is at
least

${\Pr\left[{A\setminus
B}\right]}\geq{\Pr\left[{A}\right]}-{\Pr\left[{B}\right]}\geq\frac{6}{7}-\frac{1}{7}>\frac{2}{3},$

where the second inequality follows from Lemmas 6.2 and 6.3.

For a corruption adversary, we use the same argument combined with [KRV23,
Lemma 1.8]. ∎

###### Proof of Theorem 1.5.

The proof (for both erasures and corruptions) is identical to the above proof
of Theorem 1.4, Part 1, except that we use Lemma 6.4 instead of Lemma 6.3. ∎

We next state our main result for _fixed-rate_ adversaries, showing that the
threshold rate is arbitrarily close to $1$. The proof appears in Section 6.1.
A matching negative result is established in [KRV23], see Theorems 1.5 and 1.7
there.

######  Proposition 6.5.

Fix $\epsilon>0$, $t<1$ and a local property $\mathcal{P}$ of sequences
$f\colon[n]\to\mathbb{R}$, where
$n\geq\frac{C\left(\log\frac{1}{\epsilon}+\log\frac{1}{1-t}\right)^{2}}{\epsilon^{2}(1-t)}$
for a large enough constant $C>0$. There exists a (one-sided error)
$\epsilon$-tester for $\mathcal{P}$ that works in the presence of a $t$-online
erasure fixed-rate adversary and has query complexity
$O\left(\frac{\log(\epsilon n)}{\epsilon(1-t)}\right)$. For a corruption
adversary, the same is true without the one-sided error guarantee.

###  6.1 Online Erasure-Resilience of Pair Tester

We next prove that the pair tester is unlikely to see an erased element during
the course of the algorithm. In the following definition, we separate the
erasures into two types.

######  Definition 6.6 (Blind and relative erasures).

Consider a single loop iteration of Algorithm 5. An erasure made before the
first query in this iteration is called _blind_ (with respect to this
iteration). An erasure made after the first query but before the second query
of the iteration is called _relative_.

Relative erasures can be much more effective than blind ones in making the
tester query an erased element. For relative erasures, observe that once the
first query, $x$, in a given iteration is made, the second query can take one
of roughly $\log(\epsilon n)$ options, and its probability to encounter a
relative erasure made during the iteration is of order $1/\log(\epsilon n)$.
In contrast, Lemma 6.7 shows that the probability of any future query to see a
specific blind erasure is much smaller: $O(1/n)$.

######  Lemma 6.7 (Pair tester: marginal probability).

Consider one iteration of the loop in Algorithm 5 with parameters
$n,\mathcal{P},\epsilon,t$. Fix $z\in[n]$. The probability that $z$ is queried
in this iteration is $2/n$.

###### Proof.

Fix the value of $i$ sampled in Line 3 of Algorithm 5. Out of the $n$ pairs in
$D_{2^{i}}(n)$, exactly two contain $z$, so the probability of $z$ to be
queried is exactly $2/n$. ∎

This sharp contrast between relative and blind erasures is the reason for the
huge separation between the batch-$1$ case and the batch-$2$ case. In the
former case, both relative and blind erasures are available to the adversary,
whereas in the latter case, only blind erasures are available.

The following simple corollary bounds the probability that the pair tester
queries at least one blind erasure in the course of the algorithm.

######  Corollary 6.8.

Consider one run of Algorithm 5. Let $q$ be the number of queries made by the
tester, and let $T=tq$ denote the erasure budget for the run. The probability
that the tester encounters a blind erasure is at most $\frac{2Tq}{n}$.

###### Proof.

Consider a query $x$ made by the tester. Let $S$ be the set of blind erasures
(with respect to the current iteration) made so far. The randomness used by
Algorithm 5 to choose $x$ is independent of the set $S$ (by the structure of
the tester and since $S$ consists only of blind erasures). By Lemma 6.7, for
each query we have ${\Pr\left[{x\in S}\right]}\leq 2\left|{S}\right|/n\leq
2T/n$. The corollary follows by a union bound over all queries. ∎

We now prove that our testers are unlikely to encounter erasures for both
batch sizes.

###### Proof of Lemma 6.3.

The number of queries made by Algorithm 5 is $q=\frac{200\log(\epsilon
n)}{\epsilon}$. The total number of erasures is at most
$T=tq\leq\frac{2}{10^{4}}\log(\epsilon n)$. By Corollary 6.8, the probability
that the algorithm queries a blind erasure at least once during the course of
its run is bounded by

$\frac{2Tq}{n}\leq\frac{800\log^{2}\epsilon n}{10^{4}\cdot n}<\frac{1}{10}$

for all $n$.

Next we bound the probability that Algorithm 5 encounters a relative erasure.
The a priori probability that a viable pair $(x,y)$ (that is, any pair
$(x,y)\in D_{2^{i}}(n)$ for some choice of $i\in[0:\ell]$) is queried in a
given iteration is exactly $\frac{1}{n(\ell+1)}$, where $\ell$ is as in the
algorithm. Note that this probability does not depend on $i$. By Bayes’ rule,
conditioned on the first element being $x$, the probability of each of the
elements in the set

${\left\\{y\in[n]:\exists i\in[0:\ell]\text{ such that }(x,y)\in
D_{2^{i}}(n)\right\\}}$

to be the second query of the iteration is exactly
$\frac{1}{\ell+1}\leq\frac{2}{\log(\epsilon n)}$; all other values of $y$ have
probability zero to be queried. Therefore, for any specific relative erasure
conducted by the adversary, the probability that the second query of the
relevant iteration hits the erasure is at most $\frac{2}{\log(\epsilon n)}$.
By a union bound (noting that, by definition, each relative erasure can only
affect a single iteration of the algorithm), the probability that the
algorithm queries a relative erasure throughout its run is at most
$\frac{2}{\log(\epsilon n)}\cdot T\leq\frac{4}{10^{4}}$. The proof follows by
combining the bounds for blind and relative erasures. ∎

###### Proof of Lemma 6.4.

Set $C=1/(3\cdot 10^{5})$. In the batch size $2$ case there are no relative
erasures, since each loop iteration in the algorithm is captured by a single
batch. That is, all erasures are blind. We apply Corollary 6.8 with

$q=\frac{200\log(\epsilon n)}{\epsilon}\qquad\text{and}\qquad
T=tq\leq\frac{C\epsilon^{2}n}{\log^{2}(\epsilon n)}\cdot\frac{200\log(\epsilon
n)}{\epsilon}=\frac{200C\epsilon n}{\log(\epsilon n)}$

to bound the probability to query at least one (blind) erasure during the run
of the algorithm by

$\frac{2Tq}{n}\leq\frac{200C\epsilon}{\log(\epsilon
n)}\cdot\frac{200\log(\epsilon n)}{\epsilon}\leq 40,000C<\frac{1}{7},$

as desired. ∎

###### Proof of 6.5.

Our tester applies the pair tester (Algorithm 5) as a black box, but only at
prespecified time stamps along the way (in which the fixed-rate adversary is
known not to make erasures). Let $m=O(\epsilon^{-1}\log(\epsilon n))$ denote
the number of iterations in Algorithm 5. By definition of the fixed-rate model
(Definition 2.1), when the rate is $t<1$, there exists a sequence of integers
$i_{1}<i_{2}<\ldots<i_{m}$, which satisfies the following properties.

  * •

For each $j\in[m]$, the adversary cannot make an erasure after the query at
time $i_{j}$ is conducted.

  * •

For each $j\in[m-1]$, we have $i_{j+1}-i_{j}\leq\frac{2}{1-t}$.

Our tester in this case simulates Algorithm 5: for each $j=1,\ldots,m$ we run
iteration $j$ of the latter at timestamps $i_{j}$ and $i_{j}+1$. Note that
there is no erasure between them (so all erasures are blind). Let $q\leq
2m\cdot\frac{2}{1-t}=O\left(\frac{\log(\epsilon n)}{\epsilon(1-t)}\right)$ be
the total number of queries in our case. By Lemma 6.7, the probability that
the query at each time $i_{j}$ or $i_{j}+1$ encounters an erased element is at
most $2q/n$. By a union bound, the probability that we observe at least one
erasure along the way is bounded by

$\frac{2q}{n}\cdot m\leq\frac{1}{100},$ (8)

provided that $C$ is large enough. Now, disregarding erasures, by Lemma 6.2 if
$f$ is $\epsilon$-far from $\mathcal{P}$ then the probability that the tester
queries a violation to $\mathcal{P}$ is at least $6/7$. Combined with (8), the
proof follows for the online erasures setting. The case of online corruptions
immediately follows from [KRV23, Lemma 1.8]. ∎

###  6.2 Pair Tester for Local Properties via Shifted Interval Partitioning

The main purpose of this section is to prove Lemma 6.2, establishing the
correctness of the pair tester in the offline setting. We first present and
analyze Algorithm 6, a randomly shifted version of the structured tester from
[Ben19] for local properties. We then show that the pair tester can simulate
the shifted structured tester.

The next two definitions present a hierarchical partition structure of
intervals (with some overlaps between endpoints of intervals), used in
Algorithm 6.

######  Definition 6.9 (Shifted hierarchical partition).

Let $a,n,w\in[n]$ and let $\ell\geq 0$ be an integer, where $w$ is divisible
by $2^{\ell}$ and $a+w\leq n$. An _$a$ -shifted hierarchical partition of
width $w$ with $\ell$ layers_ in $[n]$, or _$a$ -shifted
$(\ell,w)$-hierarchical partition_ in short, is a tuple
$(T_{0},\ldots,T_{\ell})$ where for each $i\in[0:\ell]$, the $i$-th layer
$T_{i}$ is a set of intervals defined by

$T_{i}=\\{[a+j\cdot 2^{i}:a+(j+1)\cdot 2^{i}]\ \ |\ \
j\in[w/2^{i}-2]\\}\quad\bigcup\quad\left\\{[1:a+2^{i}],[a+w-2^{i}:n]\right\\}.$

In other words, each layer $T_{i}$ consists of intervals of length $2^{i}+1$,
except the first interval (starting at 1) and the last interval (ending at
$n$), which may be longer. The intervals in each layer $T_{i}$ intersect only
at their endpoints.

The first and last intervals in each layer $T_{i}$ play a special role in our
analysis.

######  Definition 6.10 (Extremal intervals).

Let $T$ be an $a$-shifted $(\ell,w)$-hierarchical partition of $[n]$. An
interval $I=[x:y]\in T_{i}$ is said to be _left-extremal_ if $x=1$ and _right-
extremal_ if $y=n$. In either of these cases, $I$ is considered _extremal_.

The _query-pair_ of an interval $I$ with respect to $T$ and $i$, denoted
$Q_{T,i}(I)$, is defined as $\\{x,y\\}$ if $I$ is not extremal,
$\\{a,a+2^{i}\\}$ if $I$ is left-extremal, and $\\{a+w-2^{i},a+w\\}$ if $I$ is
right-extremal.

Equipped with a shifted hierarchical partition structure, we now present the
algorithm.

Input : local property $\mathcal{P}$, $\epsilon\in(0,1)$; query access to
$f:[n]\to\mathbb{R}$ (in offline model)

1 Set $\ell=\lfloor\log\left(\frac{\epsilon n}{4}\right)\rfloor$.

2 Let $w\in\mathbb{N}$ be the maximum integer divisible by $2^{\ell}$ and
satisfying $w\leq n-\epsilon n/4$.

3 repeat  _$\frac{20\log(\epsilon n)}{\epsilon}$_ times

4 Sample $a\in[\lceil\epsilon n/4\rceil]$ uniformly at random.

5 Let $T=(T_{0},\ldots,T_{\ell})$ be the $a$-shifted $(\ell,w)$-hierarchical
partition of $[n]$.

6 Sample a uniformly random $i\in[0:\ell]$ and a uniformly random interval
$[x,y]\in T_{i}$ .

7 Query $f(x^{\prime})$ and $f(y^{\prime})$, where
$\\{x^{\prime},y^{\prime}\\}=Q_{T,i}([x,y])$.

8 if  _$f$ is unrepairable on $\\{x^{\prime},y^{\prime}\\}$_ then

9 Reject

10

Accept

Algorithm 6 Shifted hierarchical structured tester for local properties in
offline model

The following lemma establishes that Algorithm 6 is an $\epsilon$-tester for
local properties in the standard _offline_ model of property testing.

######  Lemma 6.11.

Let $n\in\mathbb{N}$ and $\mathcal{P}$ be a local property of sequences
$f\colon[n]\to\mathbb{R}$. Algorithm 6 is an $\epsilon$-tester for
$\mathcal{P}$ with one-sided error and success probability $6/7$ in the
offline model (with no erasures/corruptions).

For the proof, we define the following notion of a witness interval.

######  Definition 6.12 (Witness interval).

Let $\mathcal{P}$ be a local property of length-$n$ sequences, and
$\mathcal{F}$ be the family of forbidden patterns characterizing
$\mathcal{P}$. The interval $I=[a:b]$ is said to be a _witness interval_ for
the sequence $f\colon[n]\to\mathbb{R}$ not satisfying $\mathcal{P}$, if one of
the following holds:

  * •

$a>1$ and $b<n$, and all sequences $f^{\prime}\colon[b-a+1]\to\mathbb{R}$,
where $f^{\prime}(1)=f(a)$ and $f^{\prime}(b-a+1)=f(b)$, contain at least one
copy of a (forbidden) pattern from $\mathcal{F}$.

  * •

$a=1$, and all sequences $f^{\prime}\colon[b]\to\mathbb{R}$ with
$f^{\prime}(b)=f(b)$ contain a pattern from $\mathcal{F}$.

  * •

$b=n$, and all $f^{\prime}\colon[n-a+1]\to\mathbb{R}$ with
$f^{\prime}(1)=f(a)$ contain a pattern from $\mathcal{F}$.

Let $T=(T_{0},T_{1},\ldots,T_{\ell})$ be an $a$-shifted
$(\ell,w)$-hierarchical partition of $[n]$. For all $i,j\in[0:\ell]$, an
interval $J\in T_{j}$ is an _ancestor_ of an interval $I\in T_{i}$ if $i<j$
and $I\subset J$. For $i<\ell$, the _parent_ of $I$ is its unique ancestor in
$T_{i+1}$. An interval $I$ in $\bigcup_{i=0}^{\ell}T_{i}$ is a _maximal
witness_ (with respect to $f,\mathcal{P},T$) if $I$ is a witness interval for
$f$ with respect to $\mathcal{P}$, while all ancestors of $I$ are not
witnesses.

To know whether $[a:b]$ is a witness interval for $f$ with respect to a given
property, one only needs to query $f(a)$ and $f(b)$ in the case that $a>1$ and
$b<n$; only $f(b)$ when $a=1$; and only $f(a)$ when $b=n$. The main structural
statement connecting being far from a property $\mathcal{P}$ and the structure
of witness intervals for $f$ in the hierarchical partition is as follows.

######  Lemma 6.13.

Let $f\colon[n]\to\mathbb{R}$ be $\epsilon$-far from a local property
$\mathcal{P}$. Let $T=(T_{0},\ldots,T_{\ell})$ be an $a$-shifted
$(\ell,w)$-hierarchical partition of $[n]$, where $a\leq\lceil\epsilon
n/4\rceil$, and $\ell$ and $w$ are as defined in Algorithm 6. The set
$\mathcal{U}$ of all maximal witness intervals in $f$ with respect to $T$ and
$\mathcal{P}$ satisfies:999Note that $T_{i}$ and $T_{i}\cap\mathcal{U}$ are
collections of sets; for example, $|T_{i}|$ is the _number of intervals_ in
$T_{i}$ (and not, say, the total number of elements in all intervals in
$T_{i}$).

$\sum_{i=0}^{\ell}\frac{|T_{i}\cap\mathcal{U}|}{|T_{i}|}\geq\frac{\epsilon}{8}.$

###### Proof.

If $T_{\ell}\cap\mathcal{U}\neq\emptyset$, the lemma follows since
$|T_{\ell}|\leq\frac{n}{\epsilon n/8}=\frac{8}{\epsilon}$. Otherwise, each
$I\in\mathcal{U}$ has a (non-witness) parent $P(I)$ in $T$. For convenience,
for each interval $I$, define $g(I):=I\cap[a:a+w]$.

We first claim that $|g(P(I))|=2|g(I)|-1$. Indeed, for $I\in T_{i}$ for some
$i\in[0:\ell]$, we have

$|g(I)|=2^{i}+1\quad\text{and}\quad|g(P(I))|=2^{i+1}+1=2|g(I)|-1.$ (9)

Note that the above is trivial for non-extremal intervals, and follows from
definition for the extremal ones. Consequently,

$1+\sum_{I\in\mathcal{U}}|g(P(I))|\leq 2\sum_{I\in\mathcal{U}}|g(I)|.$ (10)

We now bound the left-hand side from below, assuming that $f$ is
$\epsilon$-far from $\mathcal{P}$. For any interval $I=[b:c]$, define its set
of endpoints as $\\{b,c\\}\setminus\\{1,n\\}$, and define the interior
$\textsf{Int}(I)$ of $I$ as the set of all non-endpoint elements in $I$. Let

$S=\bigcup_{I\in\mathcal{U}}\textsf{Int}(P(I))\ \cup\ [1:a]\ \cup\ [a+w:n].$

######  Claim 6.14.

There exists $f^{\prime}\in\mathcal{P}$ such that $f^{\prime}(x)=f(x)$ for all
$x\in[n]\setminus S$.

###### Proof.

Let $\mathcal{F}$ be the forbidden family characterizing $\mathcal{P}$.

First, for any pair of consecutive elements $j,j+1$ which both belong to
$[n]\setminus S$, consider the interval $A_{j}=[j:j+1]\in T_{0}$. This
interval is not contained in an interval from $\mathcal{U}$. By the maximality
of $\mathcal{U}$, the interval $A_{j}$ must be a non-witness, meaning that
$(f(j),f(j+1))\notin\mathcal{F}$.

Let $L$ denote the minimal interval in $T$ which contains $[1:a+1]$ and is a
non-witness. Note that either $L=[1:a+1]$ or $L=P(I)$ for some
$I\in\mathcal{U}$. Define $R$ similarly replacing $[1:a+1]$ with $[a+w-1:n]$.
The intervals $L,R$ and all intervals $P(I)$, for $I\in\mathcal{U}$, are non-
witnesses (by definition of $\mathcal{U}$). Thus, one can remove all
$\mathcal{F}$-copies from these intervals by only modifying their interiors.

Let $f^{\prime}$ be the sequence resulting from $f$ by making these
modifications (only in interiors of intervals from
$\\{L,R\\}\cup\\{P(I):I\in\mathcal{U}\\}$; for all other elements $x$, we set
$f^{\prime}(x)=f(x)$). Observe that $f^{\prime}(x)=f(x)$ for $x\notin S$.
Indeed, since
$\textsf{Int}(L)\subseteq[1:a]\cup\bigcup_{I\in\mathcal{U}}\textsf{Int}(P(I))$
and
$\textsf{Int}(R)\subseteq[a+w:n]\cup\bigcup_{I\in\mathcal{U}}\textsf{Int}(P(I))$,
the modified elements all lie in $S$.

Our choice of $f^{\prime}$ implies that
$(f^{\prime}(j),f^{\prime}(j+1))\notin\mathcal{F}$ for each pair of elements
$\\{j,j+1\\}$ with nonempty intersection with $S$. For pairs
$\\{j,j+1\\}\subseteq n\setminus{S}$, we have seen in the first paragraph that
$(f(j),f(j+1))\notin\mathcal{F}$. Since $j,j+1\notin S$, we have
$f^{\prime}(j)=f(j)$ and $f^{\prime}(j+1)=f(j+1)$. Hence,
$(f^{\prime}(j),f^{\prime}(j+1))\notin\mathcal{F}$. Thus, $f^{\prime}$ does
not contain $\mathcal{F}$-copies, completing the proof of 6.14. ∎

We now complete the proof of Lemma 6.13. Since $f$ is $\epsilon$-far from
$\mathcal{P}$, we have that $|S|\geq\epsilon n$. On the other hand,
$|[1:a]|+|[a+w:n]|=n-w+1\leq\frac{\epsilon n}{4}+2^{\ell}+1\leq\frac{\epsilon
n}{2}+1$ and so $\bigcup_{I\in\mathcal{U}}|g(P(I))|\geq\epsilon
n-\frac{\epsilon n}{2}-1=\frac{\epsilon n}{2}-1$. From (10), we conclude that
$\sum_{I\in\mathcal{U}}|g(I)|\geq\frac{\epsilon n}{4}$.

Since $|T_{i}|\leq n/2^{i}$ for all $i\in[0:\ell]$, we derive the statement of
the lemma:

$\sum_{i=0}^{\ell}\frac{|T_{i}\cap\mathcal{U}|}{|T_{i}|}\geq\sum_{i=0}^{\ell}\sum_{I\in
T_{i}\cap\mathcal{U}}\frac{2^{i}}{n}\geq\frac{1}{n}\sum_{i=0}^{\ell}\sum_{I\in
T_{i}\cap\mathcal{U}}\frac{|g(I)|}{2}\geq\frac{\epsilon}{8},$

where in the second inequality we used the fact that $|g(I)|=2^{i}+1\leq
2^{i+1}$, established above. ∎

###### Proof of Lemma 6.11.

The tester always accepts when $f$ satisfies $\mathcal{P}$. Suppose now that
$f$ is $\epsilon$-far from $\mathcal{P}$. Let $T$ and $\mathcal{U}$ be as
guaranteed in the statement of Lemma 6.13. Consider a specific iteration of
the loop in Algorithm 6. For a specific value of $i\in{[0:\ell]}$, the
probability that the tester rejects is at least
$\frac{|T_{i}\cap\mathcal{U}|}{|T_{i}|}$. Thus, the rejection probability for
$i$ sampled uniformly from that range is at least

$\frac{1}{\ell+1}\sum_{i=0}^{\ell}\frac{|T_{i}\cap\mathcal{U}|}{|T_{i}|}\geq\frac{1}{\log(\epsilon
n)}\cdot\frac{\epsilon}{8}=\frac{\epsilon}{8\log(\epsilon n)},$

where the inequality follows from Lemma 6.13. That is, the rejection
probability in a single iteration is at least $\alpha=\epsilon/8\log(\epsilon
n)$, independently of other rounds. After
$5/(2\alpha)=20\epsilon^{-1}\log(\epsilon n)$ iterations, the probability that
the tester accepts is at most $(1-\alpha)^{5/(2\alpha)}<1/7$, and it correctly
rejects otherwise. ∎

######  Lemma 6.15 (Marginal probability for pairs in structured tester).

Let $\epsilon>0$ and $n\geq 16/\epsilon$. Let $\ell$ be as in Algorithm 6. For
$x,y\in[n]$, where $x<y,$ the probability that $x$ and $y$ are queried in Line
6 of Algorithm 6 is at most $\frac{8}{n\log(\epsilon n)}$ if $y-x=2^{i}$ for
some $i\in[0:\ell]$, and equals zero otherwise.

###### Proof.

The definition of a query-pair $Q_{T,i}(\cdot)$ immediately implies the
probability zero statement.

Fix $i\in[0:\ell]$. Denote by $E_{i}$ the event that $i$ was sampled in Line 6
of Algorithm 6. Note that
${\Pr\left[{E_{i}}\right]}=\frac{1}{\ell+1}<\frac{2}{\log(\epsilon n)}$. For
$x$ to be queried in a certain iteration (conditioned on $E_{i}$), the
following two events must take place:

  * •

Event A: $x-a$ is an integer multiple of $2^{i}$, for $a$ as defined in Line 4
of Algorithm 6.

  * •

Event B: An interval sampled in Line 6 leads to $x$ being queried.

We start by bounding ${\Pr\left[{A|E_{i}}\right]}$. The number of multiples of
$2^{i}$ in an interval of length $m=\lceil\epsilon n/4\rceil$ is at most
$\frac{\epsilon n}{4\cdot 2^{i}}+1\leq\frac{\epsilon n}{2^{i+1}}$. Since
$a\in[m]$ is picked uniformly at random,
${\Pr\left[{A|E_{i}}\right]}\leq\frac{\epsilon
n}{2^{i+1}}\cdot\frac{4}{\epsilon n}\leq\frac{1}{2^{i-1}}.$ We next bound
${\Pr\left[{B|A,E_{i}}\right]}$. There are at least $n/2^{i+1}$ intervals in
$T_{i}$, out of which at most one leads to $x$ being queried. Thus
${\Pr\left[{B|A,E_{i}}\right]}\leq\frac{2^{i+1}}{n}$. Combining all of our
bounds, we have

${\Pr\left[{B\wedge A\wedge
E_{i}}\right]}={\Pr\left[{B|A,E_{i}}\right]}\cdot{\Pr\left[{A|E_{i}}\right]}\cdot{\Pr\left[{E_{i}}\right]}\leq\frac{2^{i+1}}{n}\cdot\frac{1}{2^{i-1}}\cdot\frac{2}{\log(\epsilon
n)}=\frac{8}{n\log(\epsilon n)}.\qed$

Lemma 6.15 allows us to show that Algorithm 5 can in a strong sense “simulate”
the structured tester in Algorithm 6. In the following lemma, we use such a
simulation argument to prove that Algorithm 5 is indeed a valid pair tester
(in an _offline_ setting) for $\mathcal{P}$.

###### Proof of Lemma 6.2.

By Lemma 6.11, Algorithm 6 is an $\epsilon$-tester for $\mathcal{P}$ with one-
sided error in the offline model. We couple a single run of Algorithm 6 with
parameters $n,\mathcal{P},\epsilon$ with a single run of Algorithm 5 with the
same parameters. Specifically, we couple (i) each iteration of the loop in
Algorithm 6 with (ii) ten iterations of the loop in Algorithm 5.

For each pair $(x,y)\in D_{d}(n)$, if $d$ is not of the form $d=2^{i}$ for
$i\in[0:\ell]$ (for $\ell$ as defined in both algorithms), then the
probability that $x$ and $y$ are queried in both setups (i) and (ii) is zero.
Suppose now that $d=2^{i}$ for $i\in[0:\ell]$. By Lemma 6.15, the probability
that $x$ and $y$ are queried in setting (i) is at most
$\frac{8}{n\log(\epsilon n)}$. In Algorithm 5, the probability that $x$ and
$y$ are queried in a single iteration of the loop is at least
$\frac{1}{n}\cdot\frac{1}{\log(\epsilon n)}=\frac{1}{n\log(\epsilon n)}$. Each
of the ten iterations in setting (ii) is independent, and so the probability
that $(x,y)$ is _not_ queried in any of these iterations is bounded by
$\left(1-\frac{1}{n\log(\epsilon n)}\right)^{10}<1-\frac{8}{n\log(\epsilon
n)}$. That is, $(x,y)$ is queried in at least one iteration with probability
at least $\frac{8}{n\log(\epsilon n)}$. The lemma follows since loop
iterations in both algorithms are independent. ∎

###  6.3 Impossibility Result: No Tester for $\omega(\epsilon)$ Erasure Rate

###### Proof of Theorem 1.4, Item 2 (impossibility).

Let $\epsilon\in\big{(}0,\frac{1}{3}\big{]}$. Let $n\in\mathbb{N}$ be even.
Using the same notation as in [KRV23], we define the following distributions
$\mathcal{D}^{+}$ and $\mathcal{D}^{-}$ over functions $f:[n]\to[n]$. This is
the construction proposed and analyzed in [KRV23], but we replaced $1/3$ with
$\epsilon.$

#####  $\mathcal{D}^{+}$ distribution:

independently for all $i\in[n/2]$:

  * •

$f(2i-1)=f(2i)=2i-1$ with probability $\epsilon$. (In this case, we call
$(2i-1,2i)$ a “low pair”.)

  * •

$f(2i-1)=f(2i)=2i$ with probability $\epsilon$. (Here we call $(2i-1,2i)$ a
“high pair.”)

  * •

$f(2i-1)=2i-1$ and $f(2i)=2i$ with probability $1-2\epsilon$. (“Increasing
pair.”)

#####  $\mathcal{D}^{-}$ distribution:

independently for all $i\in[n/2]$:

  * •

$f(2i-1)=2i$ and $f(2i)=2i-1$ with probability $\epsilon$. (“Violating pair.”)

  * •

$f(2i-1)=2i-1$ and $f(2i)=2i$ with probability $1-\epsilon$. (Increasing
pair.)

All functions $f\in\mathcal{D}^{+}$ are monotone, whereas the expected
distance of a function $f\in\mathcal{D}^{-}$ from monotonicity is $\epsilon$.
It is straightforward to verify using Chernoff bound that the distance of
$f\in\mathcal{D}^{-}$ to monotonicity is bigger than $\epsilon/2$ with
probability $99/100$ as long as, say, $n>20/\epsilon$; see the discussion of
Yao’s minimax principle after 4.1 and [KRV23, Corollary 9.4] for more details.

Consider the following budget-managing adversary in the erasure
model.101010Our description of the adversarial strategy assumes that the
adversary knows whether $f$ was generated from $\mathcal{D}^{+}$ or
$\mathcal{D}^{-}$. However, this assumption is not really needed: the only
function that can be generated with nonzero probability from both of these
distributions is the identity function $f(x)=x$ for all $x$, and since the
generation probability is exponentially small in $n$, this does not materially
affect the analysis.

  * •

When $f\in\mathcal{D}^{-}$: If the tester queries an element of a violating
pair, then the adversary erases the other element of this pair (i.e., the
adversary erases $2i$ if $2i-1$ was queried, and vice versa). If the tester
queries an element of an increasing pair, then the adversary erases the other
element with probability $\epsilon/(1-\epsilon)$.

  * •

When $f\in\mathcal{D}^{+}$: If the tester queries an element of a low pair or
a high pair, the adversary erases the other element. Otherwise (the increasing
pair case), the adversary does not erase.

##### Indistinguishability of $\mathcal{D}^{+}$ and $\mathcal{D}^{-}$ under
adversarial erasures.

We claim the tester cannot distinguish these two distributions given the above
adversarial strategy. Indeed, first observe that if an element $x$ was queried
and its paired element was not erased, then they necessarily constitute an
increasing pair. Thus, the only information that the adversary can extract by
querying the element $x^{\prime}$ paired to $x$ is the probability that
$x^{\prime}$ is subsequently erased after $x$ is queried, conditioned on the
value of $f(x)$.

Suppose that, say, $x=2i-1$ (the case $x=2i$ is symmetric). First, consider
distribution $\mathcal{D}^{+}$. If $f(x)=x=2i-1$, then we are either at the
“low pair” or “increasing pair” case, and the other element $x^{\prime}$ is
erased only in the low pair case. This happens with probability

$\frac{\epsilon}{\epsilon+(1-2\epsilon)}=\frac{\epsilon}{1-\epsilon}.$

If $f(x)=2i=x+1$ in this case, then we are in the “high pair” category, and
$x^{\prime}$ is erased with probability $1$. For the $\mathcal{D}^{-}$
distribution, by definition of the adversary, it erases $x^{\prime}$ if
$f(x)=x$ with probability $\epsilon/(1-\epsilon)$, and with probability $1$ if
$f(x)=x+1$. Thus, the probabilities are equal for both distributions.

##### Budget analysis.

It remains to verify that for an adversarial erasure rate of $C\cdot\epsilon$
for some large enough absolute constant $C$, the adversary’s budget suffices
to run the above strategy at all times. We do so using a combination of Markov
inequality (for the earlier parts of the process) and Chernoff inequality (for
the later parts).

For any round $i\in\mathbb{N}$ of the process, let $X_{i}$ denote the random
variable indicating whether the tester queried an element from a previous
unqueried non-increasing pair of $f$. Note that the probability of each
$X_{i}$, even conditioned on all previous outcomes, is at most $2\epsilon$.
Denote $Y_{\ell}=\sum_{i=1}^{\ell}X_{i}$ and note that
$\mathbb{E}[Y_{\ell}]\leq 2\epsilon\cdot\ell$. Let $\ell_{0}=2/(\epsilon\cdot
C)$ be a crude upper bound for the time it takes the adversary to add an
erasure to its budget. By time $\ell_{0}m$ the adversary has a budget of at
least $m$ erasures. Note that if $Y_{\ell_{0}m}<m$ for all $m\in\mathbb{N}$
then the adversary has sufficient erasure budget at all times, as time steps
in between follow automatically. Thus, in any execution where the adversary
fails, there must exist some $m\in\mathbb{N}$ for which $Y_{\ell_{0}m}\geq m$.
We denote these bad events by $Z_{m}$ (for any $m\in\mathbb{N}$), and bound
the probability of any of these events ever happening. We use Chernoff
inequality with the upper bound on the expectation:

${\Pr\left[{Z_{m}}\right]}={\Pr\left[{Y_{\ell_{0}m}\geq
m}\right]}={\Pr\left[{Y_{\ell_{0}m}\geq(1+\delta)\cdot
2\epsilon\ell_{0}m}\right]}\leq\exp\left(-\frac{\delta^{2}\cdot
2\epsilon\ell_{0}m}{2+\delta}\right),$

where we set $C=60$, and $\delta=14$, so that $(1+\delta)\cdot
2\epsilon\ell_{0}=1$. This implies $\epsilon\ell_{0}=2/C=1/30$, and
$2\delta^{2}/(2+\delta)=24.5$, leading to

${\Pr\left[{Z_{m}}\right]}\leq e^{-49m/30}<(1/5)^{m}.$

Finally, by a union bound, the erasure budget is insufficient with probability
at most

${\Pr\left[{\cup_{m\in\mathbb{N}}Z_{m}}\right]}\sum_{m=1}^{\infty}{\Pr\left[{Z_{m}}\right]}<\sum_{m=1}^{\infty}\frac{1}{5^{m}}=\frac{1}{4}.$

Thus, with probability more than $3/4$, the adversary can maintain its
strategy indefinitely. ∎

## Acknowledgement

We thank Shachar Lovett for referring us to [BEHL12, KS05], which led to the
result in Section 4.

## References

  * [AJMR16] Pranjal Awasthi, Madhav Jha, Marco Molinaro, and Sofya Raskhodnikova.  Testing Lipschitz functions on hypergrid domains.  Algorithmica, 74(3):1055–1081, 2016.
  * [AKK+05] Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, and Dana Ron.  Testing Reed-Muller codes.  IEEE Transactions on Information Theory, 51(11):4032–4039, 2005.
  * [AS03] Sanjeev Arora and Madhu Sudan.  Improved low-degree testing and its applications.  Combinatorica, 23(3):365–426, 2003.
  * [BCH+96] Mihir Bellare, Don Coppersmith, Johan Håstad, Marcos A. Kiwi, and Madhu Sudan.  Linearity testing in characteristic two.  IEEE Transactions on Information Theory, 42(6):1781–1795, 1996.
  * [Bec08] József Beck.  Combinatorial Games: Tic-Tac-Toe Theory.  Cambridge: Cambridge University Press, 2008.
  * [BEHL12] Ido Ben-Eliezer, Rani Hod, and Shachar Lovett.  Random low-degree polynomials are hard to approximate.  Computational Complexity, 21(1):63–81, 2012.
  * [Bel18] Aleksandrs Belovs.  Adaptive lower bound for testing monotonicity on the line.  In Proceedings of Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 31:1–31:10, 2018.
  * [Ben19] Omri Ben-Eliezer.  Testing local properties of arrays.  In 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, pages 11:1–11:20, 2019.
  * [BFL91] László Babai, Lance Fortnow, and Carsten Lund.  Non-deterministic exponential time has two-prover interactive protocols.  Computational Complexity, 1:3–40, 1991.
  * [BFLR20] Omri Ben-Eliezer, Eldar Fischer, Amit Levi, and Ron D. Rothblum.  Hard properties with (very) short PCPPs and their applications.  In Proceedings, Innovations in Theoretical Computer Science (ITCS), pages 9:1–9:27, 2020.
  * [BFLS91] László Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy.  Checking computations in polylogarithmic time.  In Proceedings, ACM Symposium on Theory of Computing (STOC), pages 21–31, 1991.
  * [BGJ+12] Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, and David P. Woodruff.  Transitive-closure spanners.  SIAM Journal on Computing (SICOMP), 41(6):1380–1425, 2012.
  * [BGLR93] Mihir Bellare, Shafi Goldwasser, Carsten Lund, and Alexander Russell.  Efficient probabilistically checkable proofs and applications to approximations.  In Proceedings, ACM Symposium on Theory of Computing (STOC), pages 294–304, 1993.
  * [BGS98] Mihir Bellare, Oded Goldreich, and Madhu Sudan.  Free bits, PCPs, and nonapproximability-towards tight results.  SIAM Journal on Computing (SICOMP), 27(3):804–915, 1998.
  * [BKS+10] Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, and David Zuckerman.  Optimal testing of Reed-Muller codes.  In Proceedings, IEEE Symposium on Foundations of Computer Science (FOCS), pages 488–497, 2010.
  * [BLR93] Manuel Blum, Michael Luby, and Ronitt Rubinfeld.  Self-testing/correcting with applications to numerical problems.  Journal of Computer and System Sciences, 47(3):549–595, 1993.
  * [BRY14] Piotr Berman, Sofya Raskhodnikova, and Grigory Yaroslavtsev.  $L_{p}$-testing.  In Proceedings, ACM Symposium on Theory of Computing (STOC), pages 164–173, 2014.
  * [BS94] Mihir Bellare and Madhu Sudan.  Improved non-approximability results.  In Proceedings, ACM Symposium on Theory of Computing (STOC), pages 184–193, 1994.
  * [BSVW03] Eli Ben-Sasson, Madhu Sudan, Salil P. Vadhan, and Avi Wigderson.  Randomness-efficient low degree tests and short PCPs via epsilon-biased sets.  In Proceedings, ACM Symposium on Theory of Computing (STOC), pages 612–621, 2003.
  * [CDJS17] Deeparnab Chakrabarty, Kashyap Dixit, Madhav Jha, and C. Seshadhri.  Property testing on product distributions: Optimal testers for bounded derivative properties.  ACM Transactions on Algorithms (TALG), 13(2):20:1–20:30, 2017.
  * [CS13] Deeparnab Chakrabarty and C. Seshadhri.  Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids.  In Proceedings, ACM Symposium on Theory of Computing (STOC), 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.
  * [DG13] Irit Dinur and Venkatesan Guruswami.  PCPs via low-degree long code and hardness for constrained hypergraph coloring.  In Proceedings, IEEE Symposium on Foundations of Computer Science (FOCS), pages 340–349, 2013.
  * [DGL+99] Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, and Alex Samorodnitsky.  Improved testing algorithms for monotonicity.  In Proceedings of Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), 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 Theory of Cryptography Conference (TCC), pages 418–436, 2013.
  * [DRTV18] Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, and Nithin Varma.  Erasure-resilient property testing.  SIAM Journal on Computing (SICOMP), 47(2):295–329, 2018.
  * [EKK+00] Funda Ergün, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld, and Mahesh Viswanathan.  Spot-checkers.  Journal of Computer and System Sciences, 60(3):717–751, 2000.
  * [FGL+96] Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, and Mario Szegedy.  Interactive proofs and the hardness of approximating cliques.  Journal of the ACM, 43(2):268–292, 1996.
  * [FS95] Katalin Friedl and Madhu Sudan.  Some improvements to total degree tests.  In Third Israel Symposium on Theory of Computing and Systems (ISTCS), pages 190–198, 1995.
  * [GLR+91] Peter Gemmell, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan, and Avi Wigderson.  Self-testing/correcting for polynomials and for approximate functions.  In Proceedings, ACM Symposium on Theory of Computing (STOC), pages 32–42, 1991.
  * [GR17] Oded Goldreich and Dana Ron.  On learning and testing dynamic environments.  Journal of the ACM (JACM), 64(3):1–90, 2017.
  * [HKSS14] Dan Hefetz, Michael Krivelevich, Miloš Stojaković, and Tibor Szabó.  Positional Games.  Oberwolfach Seminars. Vol. 44. Basel: Birkhäuser Verlag GmbH, 2014.
  * [HSS13] Elad Haramaty, Amir Shpilka, and Madhu Sudan.  Optimal testing of multivariate polynomials over small prime fields.  SIAM Journal on Computing (SICOMP), 42(2):536–562, 2013.
  * [HW03] Johan Håstad and Avi Wigderson.  Simple analysis of graph tests for linearity and PCP.  Random Structures and Algorithms, 22(2):139–160, 2003.
  * [JPRZ09] Charanjit S. Jutla, Anindya C. Patthak, Atri Rudra, and David Zuckerman.  Testing low-degree polynomials over prime fields.  Random Structures and Algorithms, 35(2):163–193, 2009.
  * [JR13] Madhav Jha and Sofya Raskhodnikova.  Testing and reconstruction of Lipschitz functions with applications to data privacy.  SIAM Journal on Computing (SICOMP), 42(2):700–731, 2013.
  * [KLX10] Tali Kaufman, Simon Litsyn, and Ning Xie.  Breaking the epsilon-soundness bound of the linearity test over GF(2).  SIAM Journal on Computing (SICOMP), 39(5):1988–2003, 2010.
  * [KM22] Tali Kaufman and Dor Minzer.  Improved optimal testing results from global hypercontractivity.  In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 98–109. IEEE, 2022.
  * [KR06] Tali Kaufman and Dana Ron.  Testing polynomials over general fields.  SIAM Journal on Computing (SICOMP), 36(3):779–802, 2006.
  * [KRV23] Iden Kalemaj, Sofya Raskhodnikova, and Nithin Varma.  Sublinear-time computation in the presence of online erasures.  Theory of Computing, 19(1):1–48, 2023.
  * [KS05] Peter Keevash and Benny Sudakov.  Set systems with restricted cross-intersections and the minimum rank ofinclusion matrices.  SIAM Journal on Discrete Mathematics, 18(4):713–727, 2005.
  * [KS08] Tali Kaufman and Madhu Sudan.  Algebraic property testing: the role of invariance.  In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 403–412, 2008.
  * [LPRV21] Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and Nithin Varma.  Erasure-resilient sublinear-time graph algorithms.  In Proceedings, Innovations in Theoretical Computer Science (ITCS), pages 80:1–80:20, 2021.
  * [Mos17] Dana Moshkovitz.  Low-degree test with polynomially small error.  Computational Complexity, 26(3):531–582, 2017.
  * [MR08] Dana Moshkovitz and Ran Raz.  Sub-constant error low degree test of almost-linear size.  SIAM Journal on Computing (SICOMP), 38(1):140–180, 2008.
  * [MZ23] Dor Minzer and Kai Zheng.  Adversarial low degree testing.  arXiv, 2308.15441, 2023.
  * [NR21] Yonatan Nakar and Dana Ron.  Testing Dynamic Environments: Back to Basics.  In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of Leibniz International Proceedings in Informatics (LIPIcs), pages 98:1–98:20, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
  * [NV21] Ilan Newman and Nithin Varma.  New sublinear algorithms and lower bounds for LIS estimation.  In Proceedings, International Colloquium on Automata, Languages and Programming (ICALP), pages 100:1–100:20, 2021.
  * [O’D14] Ryan O’Donnell.  Analysis of Boolean Functions.  Cambridge University Press, 2014.
  * [PRV18] Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and Nithin Varma.  Parameterized property testing of functions.  ACM Transactions on Computation Theory, 9(4):17:1–17:19, 2018.
  * [PRW22] Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and Erik Waingarten.  Approximating the distance to monotonicity of boolean functions.  Random Struct. Algorithms, 60(2):233–260, 2022.
  * [Ras99] Sofya Raskhodnikova.  Monotonicity testing.  Masters Thesis, MIT, 1999.
  * [Ras16] Sofya Raskhodnikova.  Testing if an array is sorted.  Encyclopedia of Algorithms, pages 2219–2222, 2016.