Authors Iden Kalemaj, Sofya Raskhodnikova, Nithin Varma,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48
www.theoryofcomputing.org
Sublinear-Time Computation in the
Presence of Online Erasures
Iden Kalemajโ Sofya Raskhodnikovaโ Nithin Varma
Received June 13, 2022; Revised June 29, 2023; Published August 23, 2023
Abstract. We initiate the study of sublinear-time algorithms that access their input
via an online adversarial erasure oracle. After answering each input query, such
an oracle can erase ๐ก input values. Our goal is to understand the complexity of
basic computational tasks in extremely adversarial situations, where the algorithmโs
access to data is blocked during the execution of the algorithm in response to its
actions. Specifically, we focus on property testing in the model with online erasures.
We show that two fundamental properties of functions, linearity and quadraticity,
can be tested for constant ๐ก with asymptotically the same complexity as in the
standard property testing model. For linearity testing, we prove tight bounds in
terms of ๐ก, showing that the query complexity is ฮ(log ๐ก). In contrast to linearity and
quadraticity, some other properties, including sortedness and the Lipschitz property
of sequences, cannot be tested at all, even for ๐ก = 1. Our investigation leads to a
deeper understanding of the structure of violations of linearity and other widely
studied properties. We also consider implications of our results for algorithms that
are resilient to online adversarial corruptions instead of erasures.
A preliminary version of this paper appeared in the Proceedings of the 13th โInnovations in Theoretical Computer
Scienceโ Conference (ITCSโ22). [43].
โ Supported by NSF award CCF-1909612 and Boston Universityโs Deanโs Fellowship.
โ Supported by NSF award CCF-1909612.
ACM Classification: F.2
AMS Classification: 68Q25
Key words and phrases: randomized algorithms, property testing, Fourier analysis, linear
functions, quadratic functions, Lipschitz and monotone functions, sorted sequences
ยฉ 2023 Iden Kalemaj, Sofya Raskhodnikova, and Nithin Varma
c b Licensed under a Creative Commons Attribution License (CC-BY)
I DEN K ALEMAJ , S OFYA R ASKHODNIKOVA , AND N ITHIN VARMA
1 Introduction
We initiate the study of sublinear-time algorithms that compute in the presence of an online
adversary that blocks access to some data points in response to the algorithmโs queries. A
motivating scenario is when a user wishes to remove their data from a dataset due to privacy
concerns, as enabled by right to be forgotten laws such as the EU General Data Protection
Regulation [48]. The online aspect of our model suitably captures the case of individuals who
are prompted to restrict access to their data after noticing an inquiry into their or othersโ data.
The user could decide to remove their data after noticing, for example, that their phone number
is available on websites that scrape personal contact information. We choose to model such
user actions as adversarial in order to perform worst-case analysis and refrain from making
distributional and other assumptions on how the data access is affected. We give two other
motivating scenarios that are naturally adversarial and justify a worst-case analysis. In one, an
algorithm is trying to detect some fraud (e.g., tax fraud) and the adversary wants to obstruct
access to data in order to make it hard to uncover any evidence. In the other scenario, an
algorithmโs goal is to determine an optimal course of action (e.g., whether to invest in a stock or
to buy an item), whereas the adversary leads the algorithm astray by adaptively blocking access
to pertinent information.
In our model, after answering each query to the input object, the adversary can hide a small
number of input values. Our goal is to understand the complexity of basic computational tasks
in extremely adversarial situations, where the algorithmโs access to data is blocked during the
execution of the algorithm in response to its actions. Specifically, we represent the input object
as a function ๐ on an arbitrary finite domain1, which the algorithm can access by querying a
point ๐ฅ from the domain and receiving the answer ๐ช(๐ฅ) from an oracle. At the beginning of
computation, ๐ช(๐ฅ) = ๐ (๐ฅ) for all points ๐ฅ in the domain of the function. We parameterize our
model by a natural number ๐ก that controls the number of function values the adversary can
erase after the oracle answers each query2. Mathematically, we represent the oracle and the
adversary as one entity. However, it might be helpful to think of the oracle as the data holder
and of the adversary as the obstructionist. A ๐ก-online-erasure oracle can replace values ๐ช(๐ฅ) on
up to ๐ก points ๐ฅ with a special symbol โฅ, thus erasing them. The new values will be used by
the oracle to answer future queries to the corresponding points. The locations of erasures are
unknown to the algorithm. The actions of the oracle can depend on the input, the queries made
so far, and even on the publicly known code that the algorithm is running, but not on future
coin tosses of the algorithm.
We focus on investigating property testing in the presence of online erasures. In the
1Input objects such as strings, sequences, images, matrices, and graphs can all be represented as functions. For
example, an ๐ ร ๐ real-valued matrix is equivalent to a function mapping [๐]2 to โ.
2If the adversary were allowed to erase the query of the algorithm before answering it, the algorithm would
only see erased values. We give several motivating scenarios for the adversarial behavior in our model. The first
example is a situation where the adversary reacts by deleting additional data after some bank records are pulled by
authorities as part of an investigation. In the GDPR example mentioned previously, we argued that individuals
could be prompted to restrict access to their data only after noticing an inquiry into their or othersโ data. Finally, in a
legal setting, if the adversary is served a subpoena, they are legally bound to answer the query, but could nonetheless
destroy related evidence that is not included in the subpoena.
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 2
S UBLINEAR -T IME C OMPUTATION IN THE P RESENCE OF O NLINE E RASURES
property testing model, introduced by [64, 37] with the goal of formally studying sublinear-time
algorithms, a property is represented by a set ๐ซ (of functions satisfying the desired property). A
function ๐ is ๐-far from ๐ซ if ๐ differs from each function ๐ โ ๐ซ on at least an ๐ fraction of domain
points. The goal is to distinguish, with constant probability, functions ๐ โ ๐ซ from functions that
are ๐-far from ๐ซ. We call an algorithm a ๐ก-online-erasure-resilient ๐-tester for property ๐ซ if, given
parameters ๐ก โ โ and ๐ โ (0, 1), and access to an input function ๐ via a ๐ก-online-erasure oracle,
the algorithm accepts with probability at least 2/3 if ๐ โ ๐ซ and rejects with probability at least
2/3 if ๐ is ๐-far from ๐ซ.
We study the query complexity of online-erasure-resilient testing of several fundamental
properties. We show that for linearity and quadraticity of functions ๐ : {0, 1} ๐ โ {0, 1}, the
query complexity of ๐ก-online-erasure-resilient testing for constant ๐ก is asymptotically the same
as in the standard model. For linearity, we also prove tight bounds in terms of ๐ก, showing that
the query complexity is ฮ(log ๐ก). A function ๐ (๐ฅ) is linear if it can be represented as a sum
of monomials of the form ๐ฅ[๐], where ๐ฅ = (๐ฅ[1], . . . , ๐ฅ[๐]) is a vector of ๐ bits; the function is
quadratic if it can be represented as a sum of monomials of the form ๐ฅ[๐] or ๐ฅ[๐]๐ฅ[๐].
To understand the difficulty of testing in the presence of online erasures, consider the case of
linearity and ๐ก = 1. The celebrated tester for linearity in the standard property testing model was
proposed by Blum, Luby, and Rubinfeld [21]. It looks for witnesses of non-linearity that consist
of three points ๐ฅ, ๐ฆ, and ๐ฅ โ ๐ฆ satisfying ๐ (๐ฅ) + ๐ (๐ฆ) โ ๐ (๐ฅ โ ๐ฆ), where addition is mod 2, and โ
denotes bitwise XOR. Bellare et al. [8] show that if ๐ is ๐-far from linear, then a triple (๐ฅ, ๐ฆ, ๐ฅ โ ๐ฆ)
is a witness to non-linearity with probability at least ๐ when ๐ฅ, ๐ฆ โ {0, 1} ๐ are chosen uniformly
and independently at random. In our model, after ๐ฅ and ๐ฆ are queried, the oracle can erase the
value of ๐ฅ โ ๐ฆ. To overcome this, our tester considers witnesses with more points, namely, of the
form ๐ฅโ๐ ๐ (๐ฅ) โ ๐ ( ๐ฅโ๐ ๐ฅ) for sets ๐ โ {0, 1} ๐ of even size.
ร ร
Witnesses of non-quadraticity are even more complicated. The tester of Alon et al. [2] looks
for witnesses consisting of points ๐ฅ, ๐ฆ, ๐ง, and all four of their linear combinations. We describe a
two-player game that models the interaction between the tester and the adversary and give a
winning strategy for the tester-player. We also consider witness structures in which all specified
tuples are witnesses of non-quadraticity (to allow for the possibility of the adversary erasing
some points from the structure). We analyze the probability of getting a witness structure
under uniform sampling when the input function is ๐-far from quadratic. Our investigation
leads to a deeper understanding of the structure of witnesses for both properties, linearity and
quadraticity.
In contrast to linearity and quadraticity, we show that several other properties, specifically,
sortedness and the Lipschitz property of sequences, and the Lipschitz property of functions
๐ : {0, 1} ๐ โ {0, 1, 2}, cannot be tested in the presence of an online-erasure oracle, even
with ๐ก = 1, no matter how many queries the algorithm makes. Interestingly, witnesses for
these properties have a much simpler structure than witnesses for linearity and quadraticity.
Consider the case of sortedness of integer sequences, represented by functions ๐ : [๐] โ โ .
A sequence is sorted (or the corresponding function is monotone) if ๐ (๐ฅ) โค ๐ (๐ฆ) for all ๐ฅ < ๐ฆ
in [๐]. A witness of non-sortedness consists of two points ๐ฅ < ๐ฆ, such that ๐ (๐ฅ) >p๐ (๐ฆ).
In the standard model, sortedness can be ๐-tested with an algorithm that queries ๐( ๐/๐)
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 3
I DEN K ALEMAJ , S OFYA R ASKHODNIKOVA , AND N ITHIN VARMA
log ๐๐
uniform and independent points [32]. (The fastest testers for this property have ๐( ๐ ) query
complexity [29, 28, 18, 23, 12], but they make correlated queries that follow a more complicated
distribution.) Our impossibility result demonstrates that even the simplest testing strategy of
querying independent points can be thwarted by an online adversary. To prove this result,
we use sequences that are far from being sorted, but where each point is involved in only one
witness, allowing the oracle to erase the second point of the witness as soon as the first one is
queried. Using a version of Yaoโs principle that is suitable for our model, we turn these examples
into a general impossibility result for testing sortedness with a 1-online-erasure oracle.
Our impossibility result for testing sortedness uses sequences with many (specifically, ๐)
distinct integers. We show that this is not a coincidence by designing a ๐ก-online-erasure-resilient
sortedness tester that works for sequences that have ๐( ๐ ๐ก ๐ ) distinct values. However, the
2
number of distinct values does not have to be large to preclude testing the Lipschitz property
in our model. A function ๐ : [๐] โ โ , representing an ๐-integer sequence, is Lipschitz if
| ๐ (๐ฅ) โ ๐ (๐ฆ)| โค |๐ฅ โ ๐ฆ| for all ๐ฅ, ๐ฆ โ [๐]. Similarly, a function ๐ : {0, 1} ๐ โ โ is Lipschitz if
| ๐ (๐ฅ) โ ๐ (๐ฆ)| โค k๐ฅ โ ๐ฆk 1 for all ๐ฅ, ๐ฆ โ {0, 1} ๐ . We show that the Lipschitz property of sequences,
as well as ๐-variate functions, cannot be tested even when the range has size 3, even with ๐ก = 1,
no matter how many queries the algorithm makes.
Comparison to related models. Our model is closely related to (offline) erasure-resilient
testing of Dixit et al. [27]. In the model of Dixit et al., also investigated in [61, 58, 13, 54, 47, 51],
the adversary performs all erasures to the function before the execution of the algorithm. An
(offline) erasure-resilient tester is given a parameter ๐ผ โ (0, 1), an upper bound on the fraction
of the values that are erased. The adversary we consider is more powerful in the sense that it
can perform erasures online, during the execution of the tester. However, in some parameter
regimes, our oracle cannot perform as many erasures. Importantly, all three properties that we
show are impossible to test in our model, are testable in the model of Dixit et al. with essentially
the same query complexity as in the standard model [27]. It is open if there are properties that
have lower query complexity in the online model than in the offline model. The models are not
directly comparable because the erasures are budgeted differently.
Another widely studied model in property testing is that of tolerant testing [56]. As
explained by Dixit et al., every tolerant tester is also (offline) erasure-resilient with corresponding
parameters. As pointed out in [56], the BLR tester is a tolerant tester of linearity for ๐ผ significantly
smaller than ๐. Tolerant testing of linearity with distributional assumptions was studied in [46]
and tolerant testing of low-degree polynomials over large alphabets was studied in [38].
Tolerant testing of sortedness is closely related to approximating the distance to monotonicity
and estimating the longest increasing subsequence. These tasks can be performed with
polylogorithmic in ๐ number of queries [56, 1, 65]. As we showed, sortedness is impossible to
test in the presence of online erasures.
Adversarial models are also studied in related contexts, such as sampling from a stream [15],
more general stream computations [14], and dynamic algorithms [7]. Notably, in these models,
the input is formed adversarially online while the algorithm is running; there is no notion
of corrupted input. In contrast, in our model, algorithms solve problems on the original,
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 4
S UBLINEAR -T IME C OMPUTATION IN THE P RESENCE OF O NLINE E RASURES
ground-truth input while the access to the input is degrading.
1.1 Our results
We design ๐ก-online-erasure-resilient testers for linearity and quadraticity, two properties widely
studied because of their connection to probabilistically checkable proofs, hardness of approxi-
mating NP-hard problems, and coding theory. Our testers have 1-sided error, that is, they always
accept functions with the property. They are also nonadaptive, that is, their queries do not depend
on answers to previous queries. This is despite the adversary being allowed to respond online
(i.e., adaptively) to the algorithmโs queries.
Linearity. Starting from the pioneering work of [21], linearity testing has been investigated,
e.g., in [10, 11, 30, 8, 9, 71, 70, 67, 40, 16, 66, 68, 69, 44] (see [59] for a survey). Linearity can be
๐-tested in the standard property testing model with ๐(1/๐) queries by the BLR tester. We say
that a pair (๐ฅ, ๐ฆ) violates linearity if ๐ (๐ฅ) + ๐ (๐ฆ) โ ๐ (๐ฅ โ ๐ฆ). The BLR tester repeatedly selects a
uniformly random pair of domain points and rejects if it violates linearity. A tight lower bound
of ฮ(๐) on the probability that a uniformly random pair violates linearity was proven by Bellare
et al. [8] and Kaufman et al. [44].
We show that linearity can be ๐-tested with ๐(log e ๐ก/๐) queries with a ๐ก-online-erasure oracle.
Theorem 1.1. There exist a constant ๐ 0 โ (0, 1) and a 1-sided error, nonadaptive, ๐ก-online-erasure-
resilient ๐-tester for linearity ๐ ๐/4
of functions ๐ : {0, 1} โ {0, 1} that works for all ๐ก โค ๐0 ยท ๐ ยท 2 and
5/4
๐ก ๐ก
makes ๐ min ๐ log ๐ , ๐ queries.
1
Our linearity tester has query complexity ๐(1/๐) for constant ๐ก, which is optimal even in the
standard property testing model, with no erasures. The tester looks for more general witnesses
๐
of non-linearity thanรthe BLR tester, namely, it looks for tuples ๐ of elements from {0, 1} such
that ๐ฅโ๐ ๐ (๐ฅ) โ ๐ ( ๐ฅโ๐ ๐ฅ) and |๐ | is even. We call such tuples violating. The analysis of our
ร
linearity tester crucially depends on the following structural theorem.
Theorem 1.2. Let ๐ be a tuple of a fixed even size, where each element of ๐ is sampled uniformly and
independently at random from {0, 1} ๐ . If a function ๐ : {0, 1} ๐ โ {0, 1} is ๐-far from linear, then
hร ร i
Pr ๐ (๐ฅ) โ ๐ ( ๐ฅ) โฅ ๐.
๐
๐ฅโ๐ ๐ฅโ๐
Our theorem generalizes the result of [8], which dealt with the case |๐ | = 2. We remark that
the assertion in Theorem 1.2 does not hold for odd |๐ |. Consider the function ๐ (๐ฅ) = ๐ฅ[1] + 1
(mod 2), where ๐ฅ[1] is the first bit of ๐ฅ. Function ๐ is 12 -far from linear, but has no violating
tuples of odd size.
The core procedure of our linearity tester queries ฮ(log(๐ก/๐))รuniformly random points from
{0, 1} ๐ to build a reserve and then queries sums of the form ๐ฅโ๐ ๐ฅ, where ๐ is a uniformly
random tuple of reserve elements such that |๐ | is even. The quality of the reserve is the probability
that ๐ is violating. The likelihood that the procedure catches a violating tuple depends on the
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 5
I DEN K ALEMAJ , S OFYA R ASKHODNIKOVA , AND N ITHIN VARMA
quality of the reserve (which is a priori unknown to the tester) and the number of sums queried.
Instead of querying the same number of sums in each iteration of the core procedure, we obtain
a better query complexity by guessing different reserve qualities for each iteration and querying
the number of sums that is inversely proportional to the reserve quality. We decide on the
number of sums to query based on the work investment strategy by Berman, Raskhodnikova, and
Yaroslavtsev [17], which builds on an idea proposed by Levin and popularized by Goldreich [35].
Next, we show that our tester has optimal query complexity in terms of the erasure budget ๐ก.
Theorem 1.3. For all ๐ โ (0, 14 ], every ๐ก-online-erasure-resilient ๐-tester for linearity of functions
๐ : {0, 1} ๐ โ {0, 1} must make more than log2 ๐ก queries.
The main idea in the proof of Theorem 1.3 is that when a tester makes blog2 ๐กc queries, the
adversary has the budget to erase all linear combinations of the previous queries after every
step. As a result, the tester cannot distinguish a random linear function from a random function.
Quadraticity. Quadraticity and, more generally, low-degree testing have been studied,
e.g., in [6, 5, 34, 30, 33, 64, 62, 2, 3, 50, 49, 45, 66, 68, 42, 19, 39, 63, 25]. Low-degree testing is
closely related to local testing of Reed-Muller codes. The Reed-Muller code ๐(๐, ๐) consists of
codewords, each of which corresponds to all evaluations of a polynomial ๐ : {0, 1} ๐ โ {0, 1} of
degree at most ๐. A local tester for a code queries a few locations of a codeword; it accepts if the
codeword is in the code; otherwise, it rejects with probability proportional to the distance of the
codeword from the code.
In the standard property testing model, quadraticity can be ๐-tested with ๐(1/๐) queries by
the tester of Alon et al. [2] that repeatedly selects ๐ฅ, ๐ฆ, ๐ง โผ {0, 1} ๐ and queries ๐ on all of their
linear combinationsโthe points themselves, the double sums ๐ฅ โ ๐ฆ, ๐ฅ โ ๐ง, ๐ฆ โ ๐ง, and the triple
sum ๐ฅ โ ๐ฆ โ ๐ง. The tester rejects if the values of the function on all seven queried points sum to
1, since this cannot happen for a quadratic function. A tight lower bound on the probability
that the resulting 7-tuple is a witness of non-quadraticity was proved by Alon et al. [2] and
Bhattacharyya et al. [19].
We prove that quadraticity can be ๐-tested with ๐(1/๐) queries with a ๐ก-online-erasure-oracle
for constant ๐ก. Our tester can be easily modified to give a local tester for the Reed-Muller code
๐(2, ๐) that works with a ๐ก-online-erasure oracle.
Theorem 1.4. There exists a 1-sided error, nonadaptive, ๐ก-online-erasure-resilient ๐-tester for quadraticity
of functions ๐ : {0, 1} ๐ โ {0, 1} that makes ๐( 1๐ ) queries for constant ๐ก.
The dependence on ๐ก in the query complexity of our quadraticity tester is at least doubly
exponential, and it is an open question whether it can be improved. The main ideas behind our
quadraticity tester are explained in Section 1.2.
Sortedness. Sortedness testing (see [57] for a survey) was introduced by Ergun et al. [29].
log(๐๐)
Its query complexity has been pinned down to ฮ( ๐ ) by [29, 31, 24, 12].
We show that online-erasure-resilient testing of integer sequences is, in general, impossible.
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 6
S UBLINEAR -T IME C OMPUTATION IN THE P RESENCE OF O NLINE E RASURES
Theorem 1.5. For all ๐ โ (0, 12
1
], there is no 1-online-erasure-resilient ๐-tester for sortedness of integer
sequences.
p
In the case without erasures, sortedness can be tested with ๐( ๐/๐) uniform and independent
queries [32]. Theorem 1.5 implies that a uniform tester for a property does not translate into the
existence of an online-erasure-resilient tester, counter to the intuition that testers that make only
uniform and independent queries should be less prone to adversarial attacks. Our lower bound
construction demonstrates that the structure of violations to a property plays an important role
in determining whether the property is testable.
The hard sequences from the proof of Theorem 1.5 have ๐ distinct values. Pallavoor et al.
[53, 55] considered the setting when the tester is given an additional parameter ๐, the number
log ๐
of distinct elements in the sequence, and obtained an ๐( ๐ )-query tester. Two lower bounds
log ๐
apply to this setting: ฮฉ(log ๐) for nonadaptive testers [20] and ฮฉ( log log ๐ ) for all testers for the
โ
case when ๐ = ๐ 1/3 [12]. Pallavoor et al. also showed that sortedness can be tested with ๐( ๐/๐)
uniform and independent queries. We extend the result of Pallavoor et al. to the setting with
online erasures for the case when ๐ is small.
Theorem 1.6. Let ๐0 > 0 be a constant. There exists a 1-sided error, nonadaptive, ๐ก-online-erasure-
resilient
โ
๐-tester for sortedness of ๐-element sequences with at most ๐ distinct values. The tester makes
๐
๐( ๐ ) uniform and independent queries and works when ๐ < ๐๐0๐๐ก .
2
Thus, sortedness is not testable with online erasures when ๐ is large and is testable in the
setting when ๐ is small. For example, for Boolean sequences, it is testable with ๐(1/๐) queries.
The Lipschitz property. Lipschitz testing, introduced by [41], was subsequently studied
in [23, 26, 17, 4, 22]. Lipschitz testing of functions ๐ : [๐] โ {0, 1, 2} can be performed with
๐( 1๐ ) queries [41]. For functions ๐ : {0, 1} ๐ โ โ, it can be done with ๐( ๐๐ ) queries [41, 23].
We show that the Lipschitz property is impossible to test in the online-erasures model even
when the range of the function has only 3 distinct values. This applies to both domains, [๐] and
{0, 1} ๐ .
Theorem 1.7. For all ๐ โ (0, 81 ], there is no 1-online-erasure-resilient ๐-tester for the Lipschitz property
of functions ๐ : [๐] โ {0, 1, 2}. The same statement holds when the domain is {0, 1} ๐ instead of [๐].
Yaoโs minimax principle. All our lower bounds use Yaoโs minimax principle. A formulation
of Yaoโs principle suitable for our online-erasures model is described in Section 9.
1.2 The ideas behind our quadraticity tester
One challenge in generalizing the tester of Alon et al. [2] to work with an online-erasure oracle is
that its queries are correlated. First, we want to ensure that the tester can obtain function values
on tuples of the form (๐ฅ, ๐ฆ, ๐ง, ๐ฅ โ ๐ฆ, ๐ฅ โ ๐ง, ๐ฆ โ ๐ง, ๐ฅ โ ๐ฆ โ ๐ง). Then we want to ensure that, if the
original function is far from the property, the tester is likely to catch such a tuple that is also a
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 7
I DEN K ALEMAJ , S OFYA R ASKHODNIKOVA , AND N ITHIN VARMA
witness to not satisfying the property. Next, we formulate a two-player game3 that abstracts the
first task. In the game, the tester-player sees what erasures are made by the oracle-player. This
assumption is made to abstract out the most basic challenge and is not used in the algorithmsโ
analyses.
Quadraticity testing as a two-player game. Player 1 represents the tester and Player 2
represents the adversary. The players take turns drawing points, connecting points with edges,
and coloring triangles specified by drawn points, each in their own color. Player 1 wins the
game if it draws in blue all the vertices and edges of a triangle and colors the triangle blue. The
vertices represent the points ๐ฅ, ๐ฆ, ๐ง โ {0, 1} ๐ , the edges are the sums ๐ฅ โ ๐ฆ, ๐ฅ โ ๐ง, ๐ฆ โ ๐ง, and the
triangle is the sum ๐ฅ โ ๐ฆ โ ๐ง. A move of Player 1 consists of drawing a point or an edge between
two existing non-adjacent points or coloring an uncolored triangle between three existing points
(in blue). A move of Player 2 consists of at most ๐ก steps; in each step, it can draw a red edge
between existing points or color a triangle between three existing points (in red).
y1 y1
x1 x2 x3 x4 x5 x6 x1 x2 x3 x4 x5 x6
y1,1
y1 y1
x1 x2 x3 x4 x5 x6 x1 x2 x3 x4
y1,1 y1,2 y1,1 y1,2
Figure 1: Stages in the quadraticity game for ๐ก = 1, played according to the winning strategy for
Player 1: connecting the ๐ฆ-decoys from the first tree to ๐ฅ-decoys (frames 1-4); drawing ๐ง and
connecting it to ๐ฆ-decoys and an ๐ฅ-decoy (frames 5-6), and creation of a blue triangle (frames
7โ8). Frame 5 contains edges from ๐ง to two structures, each replicating frame 4. We depict only
points and edges relevant for subsequent frames.
Our online-erasure-resilient quadraticity tester is based on a winning strategy for Player 1
with ๐ก ๐(๐ก) moves. At a high level, Player 1 first draws many decoys for ๐ฅ. The ๐ฆ-decoys are
organized in ๐ก + 1 full (๐ก + 1)-ary trees of depth ๐ก. The root for tree ๐ is ๐ฆ ๐ , its children are ๐ฆ ๐,๐ ,
3This game has been tested on real children, and they spent hours playing it.
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 8
S UBLINEAR -T IME C OMPUTATION IN THE P RESENCE OF O NLINE E RASURES
where ๐ โ [๐ก + 1], etc. We jot the rest of the winning strategy for ๐ก = 1 and depict it in Fig. 1.
(๐) (๐)
In this case, Player 1 does the following for each of two trees: it draws points ๐ฅ1 , . . . , ๐ฅ 12 , ๐ฆ ๐ ;
(๐) (๐)
connects ๐ฆ ๐ to half of ๐ฅ-decoys (w.l.o.g., ๐ฅ 1 , . . . , ๐ฅ 6 ); draws point ๐ฆ ๐,1 , connects it to two of the
(๐) (๐) (๐) (๐)
๐ฅ-decoys adjacent to ๐ฆ1 (w.l.o.g., ๐ฅ 1 and ๐ฅ 2 ); draws point ๐ฆ ๐,2 , connects it to two of ๐ฅ 3 , . . . , ๐ฅ 6
(๐) (๐)
(w.l.o.g., ๐ฅ 3 and ๐ฅ 4 ); draws ๐ง and connects it to one of the roots (w.l.o.g., ๐ฆ1 ), connects ๐ง to one
(1) (1) (1)
of ๐ฆ1,1 and ๐ฆ1,2 (w.l.o.g., ๐ฆ1,1 ), connects ๐ง to one of ๐ฅ1 and ๐ฅ 2 (w.l.o.g., ๐ฅ 1 ), and finally colors
(1) (1)
one of the triangles ๐ฅ 1 ๐ฆ1 ๐ง and ๐ฅ 1 ๐ฆ1,1 ๐ง, thus winning the game. The decoys are arranged to
guarantee that Player 1 always has at least one available move in each step of the strategy.
For general ๐ก, the winning strategy is described in full detail in Algorithm 3. Recall that the
๐ฆ-decoys are organized in ๐ก + 1 full (๐ก + 1)-ary trees of depth ๐ก. For every root-to-leaf path in
every tree, Player 1 draws edges from all the nodes in that path to a separate set of ๐ก + 1 decoys
for ๐ฅ. After ๐ง is drawn, the tester โwalksโ along a root-to-leaf path in one of the trees, drawing
edges between ๐ง and the ๐ฆ-decoys on the path. The goal of this walk is to avoid the parts of the
tree spoiled by Player 2. Finally, Player 1 connects ๐ง to an ๐ฅ-decoy that is adjacent to all vertices
in the path, and then colors a triangle involving this ๐ฅ-decoy, a ๐ฆ-decoy from the chosen path,
and ๐ง. The structure of decoys guarantees that Player 1 always has ๐ก + 1 options for its next
move, only ๐ก of which can be spoiled by Player 2.
From the game to a tester. There are two important aspects of designing a tester that are
abstracted away in the game: First, the tester does not actually know which values are erased
until it queries them. Second, the tester needs to catch a witness demonstrating a violation of
the property, not merely a tuple of the right form with no erasures. Here, we briefly describe
how we overcome these challenges.
Our quadraticity tester is based directly on the game. It converts the moves of the winning
strategy of Player 1 into a corresponding procedure, making a uniformly random guess at each
step about the choices that remain nonerased. There are three core technical lemmas used in
the analysis of the algorithm. Lemma 5.4 lower bounds the probability that the tester makes
correct guesses at each step about which edges (double sums) and triangles (triple sums) remain
nonerased, thus addressing part of the first challenge. This probability depends only on the
erasure budget ๐ก. To address the second challenge, Lemma 5.3 gives a lower bound on the
probability that uniformly random sampled points (the ๐ฅ- and ๐ฆ- decoys together with ๐ง) form
a large violation structure, where all triangles that Player 1 might eventually complete violate
quadraticity. Building on a result of Alon et al., we show that even though the number of
triangles involved in the violation structure is large, namely ๐ก ๐(๐ก) , the probability of sampling
such a structure is ๐ผ = ฮฉ(min(๐, ๐ ๐ก )), where ๐ ๐ก โ (0, 1) depends only on ๐ก. Finally, Lemma 5.2
shows that despite the online adversarial erasures, the tester has a probability of ๐ผ/2 of sampling
the points of such a large violation structure and obtaining their values from the oracle. These
three lemmas combined show that quadraticity can be tested with ๐(1/๐) queries for constant ๐ก.
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 9
I DEN K ALEMAJ , S OFYA R ASKHODNIKOVA , AND N ITHIN VARMA
1.3 Sublinear-time computation in the presence of online corruptions
Our model of online erasures extends naturally to a model of online corruptions, where the
adversary is allowed to modify values of the input function. Specifically, a ๐ก-online-corruption
oracle ๐ช, after answering each query, can replace values ๐ช(๐ฅ) on up to ๐ก domain points ๐ฅ with
arbitrary values in the range of ๐ . Our algorithmic results in the presence of online erasures
have implications for computation in the presence of online corruptions.
We consider two types of computational tasks in the presence of online corruptions. The
first one is ๐ก-online-corruption-resilient testing, defined analogously to ๐ก-online-erasure-resilient
testing. Specifically, we call an algorithm a ๐ก-online-corruption-resilient ๐-tester for property ๐ซ if,
given parameters ๐ก โ โ and ๐ โ (0, 1), and access to an input function ๐ via a ๐ก-online-erasure
oracle, the algorithm accepts with probability at least 2/3 if ๐ โ ๐ซ and rejects with probability at
least 2/3 if ๐ is ๐-far from ๐ซ. In Lemma 1.8 we study a general computational task for which the
algorithm has oracle access to an input function and has to output a correct answer with high
probability. We consider algorithms that access their input via an online-erasure oracle and
show that if with high probability they output a correct answer and encounter no erased queries
during their execution, they also output a correct answer with high probability in the presence
of online corruptions. Note that the correctness of the answer is with respect to the original
function ๐ , as opposed to the corrupted values represented by ๐ช. Lemma 1.8 uses the notion
of an adversarial strategy. We model an adversarial strategy as a distribution on decision trees,
where each tree dictates the erasures to be made for a given input and queries of the algorithm.
Lemma 1.8. Let ๐ be an algorithm that is given access to a function via a ๐ก-online-erasure oracle and
performs a specified computational task. Suppose that for all adversarial strategies, with probability at
least 2/3, the algorithm ๐ outputs a correct answer and queries no erased values during its execution.
Then, for the same computational task, when ๐ is given access to a function via a ๐ก-online-corruption
oracle, it outputs a correct answer with probability at least 2/3.
This lemma can be applied to our online-erasure-resilient testers for linearity and for
sortedness with few distinct values. These testers have 1-sided error, i.e., they err only when the
function is far from the property. We can amplify the success probability of the testers to 5/6 for
functions that are far from the property, without changing the asymptotic query complexity
of the testers. In addition, the resulting testers have a small probability (specifically, at most
1/6) of encountering an erasure during their computation. As a result, Lemma 1.8 implies
online-corruption-resilient testers for these properties. Their performance is summarized in
Corollaries 8.1 and 8.2.
For the second type of computational tasks, we return to the motivation of the algorithm
looking for evidence of fraud. In Lemma 1.9, we show that every nonadaptive, 1-sided error,
online-erasure-resilient tester for any property ๐ซ can be modified so that, given access to an
input function ๐ that is far from ๐ซ via an online-corruption oracle, it outputs a witness of ๐ not
being in ๐ซ. This result applies to our testers for sortedness with few distinct values, linearity,
and quadraticity. Note that the values of the witness could be corrupted values of ๐ . For this
task, it is helpful to think of the input ๐ as changing dynamically rather than there being a
ground truth input ๐ as is the case for Lemma 1.8.
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 10
S UBLINEAR -T IME C OMPUTATION IN THE P RESENCE OF O NLINE E RASURES
Lemma 1.9. Let ๐ซ be a property of functions that has a 1-sided error, nonadaptive, ๐ก-online-erasure-
resilient tester. Then there exists a nonadaptive algorithm with the same query complexity that, given a
parameter ๐ and access via a ๐ก-online-corruption-oracle ๐ช to a function ๐ that is ๐-far from ๐ซ, outputs
with probability at least 2/3 a witness of ๐ โ ๐ซ. The witness consists of queried domain points ๐ฅ 1 , . . . , ๐ฅ ๐
and values ๐ช(๐ฅ 1 ), . . . , ๐ช(๐ฅ ๐ ) obtained by the algorithm, such that no ๐ โ ๐ซ has ๐(๐ฅ ๐ ) = ๐ช(๐ฅ ๐ ) for all
๐ โ [๐].
1.4 Conclusions and open questions
We initiate a study of sublinear-time algorithms in the presence of online adversarial erasures.
We design efficient online-erasure-resilient testers for several important properties (linearity,
quadraticity, andโfor the case of small number of distinct valuesโsortedness). For linearity,
we prove tight upper and lower bounds in terms of ๐ก. We also show that several basic properties,
specifically, sortedness of integer sequences and the Lipschitz properties, cannot be tested in
our model. We now list several open problems.
โข Sortedness is an example of a property that is impossible to test with online erasures,
but is easy to test with offline erasures, as well as tolerantly. Is there a property that
has smaller query complexity in the online-erasure-resilient model than in the (offline)
erasure-resilient model of [27]?
โข We design a ๐ก-online-erasure-resilient quadraticity tester that makes ๐(1/๐) queries for
constant ๐ก. What is the query complexity of ๐ก-online-erasure-resilient quadraticity testing
in terms of ๐ก and ๐? Specifically, the dependence on ๐ก in the query complexity of our
quadraticity tester is at least doubly exponential, and it is open whether it can be improved.
โข The query complexity of ๐-testing if a function is a polynomial of degree at most ๐ is
ฮ( 1๐ + 2 ๐ ) [2, 19]. Is there a low-degree test for ๐ โฅ 3 that works in the presence of online
erasures?
โข Our tester for linearity works in the presence of online corruptions, but our tester for
quadraticity does not. The reason for this is that our linearity tester is unlikely to see
erasures, but that is not the case for our quadraticity tester. Is there an online-corruption-
resilient quadraticity tester?
2 An online-erasure-resilient linearity tester
To prove Theorem 1.1, we present and analyze two testers. Our main online-erasure-resilient
linearity tester (Algorithm 1) is presented in this section. Its query complexity has optimal
dependence on ๐ก and nearly optimal dependence on ๐. Its performance is summarized in
Theorem 2.1. To complete the proof of Theorem 1.1, we give a ๐(๐ก/๐)-query linearity tester in
Section 3. It has optimal query complexity for constant ๐ก.
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 11
I DEN K ALEMAJ , S OFYA R ASKHODNIKOVA , AND N ITHIN VARMA
Theorem 2.1. There exists ๐ 0 โ (0, 1) and a 1-sided error, nonadaptive, ๐ก-online-erasure-resilient ๐-tester
for linearity of functions ๐ : {0, 1} ๐ โ {0, 1} that works for ๐ก โค ๐0 ยท ๐5/4 ยท 2๐/4 and makes ๐( 1๐ log ๐๐ก )
queries.
The ๐ก-online-erasure-resilient tester guaranteed by Theorem 2.1 is presented in Algorithm 1.
Algorithm 1 An Online-Erasure-Resilient Linearity Tester
Input: ๐ โ (0, 12 ), erasure budget ๐ก โ โ , access to function ๐ : {0, 1} ๐ โ {0, 1} via a ๐ก-online-
erasure oracle.
1: Let ๐ = 2 log 50๐ก๐ .
2: for all ๐ โ [log 8๐ ]:
3: repeat 82ln๐ ๐5 times:
4: for all ๐ โ [๐]:
5: Sample ๐ฅ ๐ โผ {0, 1} ๐ and query ๐ at ๐ฅ ๐ .
6: repeat 4 ยท 2 ๐ times:
7: Sample a uniform nonempty subset ๐ผ of [๐] of even size.
Query ๐ at
ร ๐โ๐ผ ๐ฅ ๐ .
ร
8:
Reject if ๐โ๐ผ ๐ (๐ฅ ๐ ) โ ๐ ( ๐โ๐ผ ๐ฅ ๐ ) and all points ๐ฅ ๐ for ๐ โ ๐ผ and ๐โ๐ผ ๐ฅ ๐ are
ร ร
9:
nonerased.
10: Accept.
2.1 Proof of Theorem 1.2
In this section, we prove Theorem 1.2, the main structural result used in Theorem 2.1. Recall
that a ๐-tuple (๐ฅ 1 , . . . , ๐ฅ ๐ ) โ ({0, 1} ๐ ) ๐ violates linearity if ๐ (๐ฅ 1 ) + ยท ยท ยท + ๐ (๐ฅ ๐ ) โ ๐ (๐ฅ1 โ ยท ยท ยท โ ๐ฅ ๐ ).
(Addition is mod 2 when adding values of Boolean functions.) Theorem 1.2 states that if ๐ is
๐-far from linear, then for all even ๐, with probability at least ๐, independently and uniformly
sampled points ๐ฅ 1 , . . . , ๐ฅ ๐ โผ {0, 1} ๐ form a violating ๐-tuple. Our proof of Theorem 1.2 builds
on the proof of [8, Theorem 1.2], which is a special case of Theorem 1.2 for ๐ = 2. The proof
is via Fourier analysis. Next, we state some standard facts and definitions related to Fourier
analysis. See, e.g., [52] for proofs of these facts.
Consider the space of all real-valued functions on {0, 1} ๐ equipped with the inner-product
h๐, โi = ๐ผ [๐(๐ฅ)โ(๐ฅ)],
๐ฅโผ{0,1} ๐
๐ ๐
ร ๐, โ : {0, 1} โ โ. The character functions ๐๐ : {0, 1} โ {โ1, 1}, defined as ๐๐ =
where
(โ1) ๐โ๐ ๐ฅ[๐] for ๐ โ [๐], form an orthonormal basis for the space of functions under consideration.
Hence, every function ๐ : {0, 1} ๐ โ โ can be uniquely expressed as a linear combination of the
functions ๐๐ , where ๐ โ [๐]. The Fourier coefficients of ๐ are the coefficients on the functions
๐๐ in this linear representation of ๐.
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 12
S UBLINEAR -T IME C OMPUTATION IN THE P RESENCE OF O NLINE E RASURES
Definition 2.2 (Fourier coefficient). For ๐ : {0, 1} ๐ โ โ and ๐ โ [๐], the Fourier coefficient of ๐
on ๐ is b
๐ (๐) = h๐, ๐๐ i = ๐ผ [๐(๐ฅ)๐๐ (๐ฅ)].
๐ฅโผ{0,1} ๐
We will need the following facts about Fourier coefficients.
Theorem 2.3 (Parsevalโs Theorem). For all functions ๐ : {0, 1} ๐ โ โ, it holds that h๐, ๐i =
๐ (๐)2 . In particular, if ๐ : {0, 1} ๐ โ {โ1, 1} then ๐โ[๐] b
๐ (๐)2 = 1.
ร ร
๐โ[๐] b
Theorem 2.4 (Plancherelโs Theorem). For all functions ๐, โ : {0, 1} ๐ โ โ, it holds that h๐, โi =
๐ (๐)b
โ(๐).
ร
๐โ[๐] b
A function ๐ : {0, 1} ๐ โ {โ1, 1} is linear if ๐(๐ฅ)๐(๐ฆ) = ๐(๐ฅ โ ๐ฆ) for all ๐ฅ, ๐ฆ โ {0, 1} ๐ .
Lemma 2.5. The distance of ๐ : {0, 1} ๐ โ {โ1, 1} to linearity is 21 โ 21 max๐โ[๐] b
๐ (๐).
Finally, we also use the convolution operation, defined below, and one of its key properties.
Definition 2.6 (Convolution). Let ๐, โ : {0, 1} ๐ โ โ. Their convolution is the function ๐ โ โ :
{0, 1} ๐ โ โ defined by (๐ โ โ)(๐ฅ) = ๐ผ [๐(๐ฆ)โ(๐ฅ โ ๐ฆ)].
๐ฆโผ{0,1} ๐
Theorem 2.7. Let ๐, โ : {0, 1} ๐ โ โ. Then, for all ๐ โ [๐], it holds ๐
ย โ โ(๐) = b
๐ (๐)b
โ(๐).
Proof of Theorem 1.2. Define ๐ : {0, 1} ๐ โ {โ1, 1} so that ๐(๐ฅ) = (โ1) ๐ (๐ฅ) . That is, ๐ is obtained
from the function ๐ by encoding its output with ยฑ1. Note that the distance to linearity of ๐ is the
same as the distance to linearity of ๐ . We have that the expression 12 โ 12 ๐(๐ฅ 1 ) . . . ๐(๐ฅ ๐ )๐(๐ฅ 1 โ ยท ยท ยท โ
๐ฅ ๐ ) is an indicator for the event that points ๐ฅ 1 , . . . , ๐ฅ ๐ โผ {0, 1} ๐ violate linearity for ๐. Define ๐ โ๐
to be the convolution of ๐ with itself ๐ times, i.e., ๐ โ๐ = ๐ โ ยท ยท ยท โ ๐, where the โ operator appears
๐ โ 1 times. We obtain
Pr [(๐ฅ 1 , . . . , ๐ฅ ๐ ) violates linearity]
๐ฅ 1 ,...,๐ฅ ๐ โผ{0,1} ๐
h1
1 i
= ๐ผ โ ๐(๐ฅ 1 ) . . . ๐(๐ฅ ๐ )๐(๐ฅ 1 โ ยท ยท ยท โ ๐ฅ ๐ )
๐ฅ1 ,...,๐ฅ ๐ โผ{0,1} ๐ 2 2
1 1
= โ ๐ผ [๐(๐ฅ 1 ) . . . ๐(๐ฅ ๐โ1 ) ยท ๐ผ [๐(๐ฅ ๐ )๐(๐ฅ1 โ ยท ยท ยท โ ๐ฅ ๐ )]]
2 2 ๐ฅ1 ,...,๐ฅ ๐โ1 โผ{0,1} ๐ ๐ฅ ๐ โผ{0,1} ๐
1 1
= โ ๐ผ [๐(๐ฅ 1 ) . . . ๐(๐ฅ ๐โ1 )(๐ โ ๐)(๐ฅ 1 โ ยท ยท ยท โ ๐ฅ ๐โ1 )] (2.1)
2 2 ๐ฅ1 ,...,๐ฅ ๐โ1 โผ{0,1} ๐
1 1
= โ ๐ผ [๐(๐ฅ1 ) ยท (๐ โ๐ )(๐ฅ1 )] (2.2)
2 2 ๐ฅ1 โผ{0,1} ๐
1 1 ร
= โ ๐ (๐)๐c
b โ๐ (๐) (2.3)
2 2
๐โ[๐]
1 1 ร
= โ ๐ (๐) ๐+1 ,
b (2.4)
2 2
๐โ[๐]
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 13
I DEN K ALEMAJ , S OFYA R ASKHODNIKOVA , AND N ITHIN VARMA
where (2.1) holds by the definition of convolution, (2.2) follows by repeated application of the
steps used to obtain (2.1), (2.3) follows from Plancherelโs Theorem (Theorem 2.4), and (2.4)
follows from Theorem 2.7.
๐ (๐)| โค 1 for all ๐ โ [๐], because b
Note that |b ๐ (๐) is the inner product of two functions with
range in {โ1, 1}. In addition, b๐ (๐) โฅ 0 for ๐ such that ๐๐ is the closest linear function to ๐. Then,
for even ๐,
ร ร
๐ (๐) ๐+1 โค max(b
b ๐ (๐) ๐โ1 ) ๐ (๐) ๐โ1 ) โค max b
๐ (๐)2 = max(b
b ๐ (๐),
๐โ[๐] ๐โ[๐] ๐โ[๐]
๐โ[๐] ๐โ[๐]
where the equality follows from Parsevalโs Theorem (Theorem 2.3). By Lemma 2.5, the distance
๐ (๐), which is at least ๐, since ๐ is ๐-far from linear. This
of ๐ to linearity is 12 โ 12 max๐โ[๐] b
concludes the proof.
2.2 Proof of Theorem 2.1
In this section, we prove Theorem 2.1 using Theorem 1.2. In Lemma 2.8, we analyze the
probability of good events that capture, roughly, that the queries made in the beginning of
each iteration havenโt already been โspoiledโ by the previous erasures. Then we use the work
investment strategy of [17], stated in Lemma 2.9, together with Theorem 1.2 and Lemma 2.8 to
prove Theorem 2.1.
Each iteration of the outer repeat loop in Steps 3-9 of Algorithm 1 is called a round. We say
a query ๐ฅ is successfully obtained if it is nonerased when queried, i.e., the tester obtains ๐ (๐ฅ) as
opposed to โฅ.
Lemma 2.8 (Good events). Fix one round of Algorithm 1. Consider ร the points ๐ฅ 1 , . . . , ๐ฅ ๐ queried in
Step 5 of this round, where ๐ = 2 log(50๐ก/๐), and the set ๐ of all sums ๐โ๐ผ ๐ฅ ๐ , where ๐ผ is a nonempty
subset of [๐] of even size. Let ๐บ1 be the (good) event that all points in ๐ are distinct. Let ๐บ2 be the
(good) event that all points ๐ฅ 1 , . . . , ๐ฅ ๐ are successfully obtained and all points in ๐ are nonerased at the
beginning of the round. Finally, let ๐บ = ๐บ1 โฉ ๐บ2 . Then Pr[๐บ] โค 2๐ for all adversarial strategies.
Proof. First, we analyze event ๐บ1 . Consider points ๐ฅ ๐1 , . . . , ๐ฅ ๐ ๐ , ๐ฅ ๐10 , . . . , ๐ฅ ๐โ0 โผ {0, 1} ๐ , where
{๐1 , . . . , ๐ ๐ } โ {๐10 , . . . , ๐โ0 }, ๐, โ โ [๐] and ๐, โ are even. Since the points are distributed uniformly
and independently, so are the sums ๐ฅ ๐1 โ ยท ยท ยท โ ๐ฅ ๐ ๐ and ๐ฅ ๐10 โ ยท ยท ยท โ ๐ฅ ๐โ0 . The probability that two
uniformly and independently sampled points ๐ฅ, ๐ฆ โผ {0, 1} ๐ are identical is 21๐ . The number of
sets ๐ผ โ [๐] of even size is 2๐โ1 because every subset of [๐ โ 1] can be uniquely completed to
such a set ๐ผ. By a union bound over all pairs of sums, Pr[๐บ1 ] โค 4ยท2 22๐
๐.
To analyze ๐บ2 , fix any adversarial strategy. The number of queries made by Algorithm 1 is
at most
log(8/๐)
ร 8 ln 5 ๐
8 ln 5 32 ln 5 8 8 ln 5 16 ln 5 40๐
๐ + 4 ยท 2 โค ๐+ log โค ๐+ ๐โค . (2.5)
2๐๐ ๐ ๐ ๐ ๐ ๐ ๐
๐=1
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 14
S UBLINEAR -T IME C OMPUTATION IN THE P RESENCE OF O NLINE E RASURES
๐ points. Since each point ๐ฅ ๐ is sampled uniformly from
40๐๐ก
Hence, the oracle erases at most
{0, 1} ๐ ,
40๐๐ก
Pr [๐ฅ ๐ is erased when queried] โค .
๐ฅ ๐ โผ{0,1} ๐ ๐ ยท 2๐
Additionally, before the queries ๐ฅ ๐ are revealed to the oracle, each sum ๐โ๐ผ ๐ฅ ๐ is distributed
ร
uniformly at random. Therefore, for every {๐1 , . . . , ๐ ๐ } โ [๐],
40๐๐ก
Pr [๐ฅ ๐1 โ ยท ยท ยท โ ๐ฅ ๐ ๐ is erased at the beginning of the round] โค .
๐ฅ ๐1 ,...,๐ฅ ๐ ๐ โผ{0,1} ๐ ๐ ยท 2๐
By a union bound over the ๐ points sampled in Step 5 and at most 2๐โ1 sums, we get
40๐๐ก 40๐๐ก ยท 2๐
Pr[๐บ2 ] โค ๐
(๐ + 2๐โ1 ) โค .
๐2 ๐ ยท 2๐
Since ๐ = 2 log 50๐ก
40๐๐ก ๐
๐ โค 4 ยท 2 and, consequently,
3
๐ , we get
22๐ 40๐๐ก ยท 2๐ 22๐ 504 ยท ๐ก 4 50 ยท ๐ 0 ยท ๐ ๐
4 4 5
Pr[๐บ] โค ๐
+ ๐
โค ๐
โค ๐
โค โค ,
4ยท2 ๐ยท2 2 ๐ 2
4 ๐ 4 2
since ๐ก โค ๐ 0 ยท ๐5/4 ยท 2๐/4 , as stated in Theorem 2.1, and assuming ๐0 is sufficiently small.
Next, we state the work investment lemma.
Lemma 2.9 (Lemma 2.5 of [17]). Let ๐ be a random variable taking values in [0, 1]. Suppose ๐ผ[๐] โฅ ๐ผ.
Let ๐ = dlog( ๐ผ4 )e and ๐ฟ โ (0, 1) be the desired probability of error. For all ๐ โ [๐ ], let ๐ ๐ = Pr[๐ โฅ 2โ๐ ]
ร๐ ๐๐
and ๐ ๐ = 4 ln(1/๐ฟ)
2๐ ๐ผ
. Then ๐=1 (1 โ ๐ ๐ ) โค ๐ฟ.
๐
Proof of Theorem 2.1. By (2.5), the query complexity of Algorithm 1 is ๐( ๐ ) = ๐( ๐ ). Algo-
log(๐ก/๐)
rithm 1 is nonadaptive and always accepts if ๐ is linear. Suppose now that ๐ is ๐-far from linear
and fix any adversarial strategy. We show that Algorithm 1 rejects with probability at least 2/3.
Consider the last round of Algorithm 1. For points ๐ฅ 1 , . . . , ๐ฅ ๐ โผ {0, 1} ๐ sampled in Step 5
of this last round, let ๐ denote the fraction of nonempty sets {๐1 , . . . , ๐ ๐ } โ [๐] such that ๐ is
even and (๐ฅ ๐1 , . . . , ๐ฅ ๐ ๐ ) violates linearity. Recall the event ๐บ defined in Lemma 2.8. Let 1๐บ be the
indicator random variable for the event ๐บ for the last round.
Claim 2.10. Let ๐ = ๐ ยท 1๐บ , where ๐ is as defined above. Then ๐ผ[๐] โฅ 2๐ .
Proof. For all nonempty {๐1 , . . . , ๐ ๐ } โ [๐], such that ๐ is even, let ๐๐1 ,...,๐ ๐ be the indicator for the
event that (๐ฅ ๐1 , . . . , ๐ฅ ๐ ๐ ) violates linearity. By Theorem 1.2 and the fact that ๐ is even,
๐ผ[๐๐1 ,...,๐ ๐ ] = Pr [(๐ฅ ๐1 , . . . , ๐ฅ ๐ ๐ ) violates linearity] โฅ ๐.
๐ฅ ๐1 ,...,๐ฅ ๐ ๐ โผ{0,1} ๐
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 15
I DEN K ALEMAJ , S OFYA R ASKHODNIKOVA , AND N ITHIN VARMA
We obtain a lower bound on ๐ผ[๐] by linearity of expectation.
1 ร
๐ผ[๐] = ๐ผ[๐๐1 ,...,๐ ๐ ] โฅ ๐. (2.6)
2๐โ1 โ 1
{๐ 1 ,...,๐ ๐ }โ[๐],๐ even
Observe that ๐ = ๐ when ๐บ occurs, and ๐ = 0 otherwise. By the law of total expectation,
๐ผ[๐] = ๐ผ[๐ |๐บ] ยท Pr[๐บ] + ๐ผ[๐ |๐บ] ยท Pr[๐บ] = ๐ผ[๐ |๐บ] ยท Pr[๐บ] = ๐ผ[๐|๐บ] ยท Pr[๐บ]
= ๐ผ[๐] โ ๐ผ[๐|๐บ] ยท Pr[๐บ] โฅ ๐ โ 1 ยท (๐/2) = ๐/2,
where the inequality follows from (2.6), the fact that ๐ โค 1, and Lemma 2.8.
Fix any round of Algorithm 1 and the value of ๐ used in this round (as defined in Step 2).
Let ๐ 0 be defined as ๐, but for this round instead of the last one. The round is special if ๐ 0 โฅ 2โ๐ .
Let ๐ 0๐ = Pr[๐ 0 โฅ 2โ๐ ] and ๐ ๐ = Pr[๐ โฅ 2โ๐ ]. Then ๐ 0๐ โฅ ๐ ๐ , since the number of erasures only
increases with each round. For each ๐, there are ๐ ๐ = 82ln๐ ๐5 rounds of Algorithm 1 that are run
with this particular value of ๐. Since Algorithm 1 uses independent random coins for each
round, the probability that no round is special is at most
log 8๐ log 8๐
ร ร 1
(1 โ ๐ 0๐ ) ๐ ๐ โค (1 โ ๐ ๐ ) ๐ ๐ โค ,
5
๐=1 ๐=1
where the last inequality follows by Lemma 2.9 applied with ๐ฟ = 1/5 and ๐ผ = ๐/2 and Claim 2.10.
Therefore, with probability at least 45 , Algorithm 1 has a special round.
Consider a special round of Algorithm 1 and fix the value of ๐ for this round. We show ร that
Algorithm 1 rejects in the special round with probability at least 5/6. We call a sum ๐โ๐ผ ๐ฅ ๐
violating if the tuple (๐ฅ ๐ : ๐ โ ๐ผ) violates linearity. Since ๐บ occurred, all ๐ points queried in Step 5
of Algorithm 1 were successfully obtained. So, the algorithm will reject as soon as it successfully
obtains a violating sum. Since ๐บ occurred, there are at least 2๐โ1 โ 1 distinct sums that can be
queried in Step 8, all of them nonerased at the beginning of the round. Algorithm 1 makes at
most ๐ + 4 ยท 2 ๐ queries in this round, and thus the fraction of these sums erased during the round
is at most
๐ + 4 ยท 2๐ 3 ยท 2๐
1 ๐ก 12๐ก ยท 2 ๐
๐ก ยท ๐โ1 โค๐กยท + ๐โ2 โค +
2 โ1 2๐/2 2 ๐ก ยท 50
๐ ๐ก 2 ยท ( 50
๐)
2
8 12 ยท 82 ยท 2 ๐ 0.16 0.3072 1
= + โค ๐
+ ๐
โค ,
50 ยท ๐ 8
502 ๐ก ยท ( 8๐ )2 2 2 2 ยท 2๐
๐
where in the first inequality we used that 2๐โ1 โ1 โค 2๐/2
1
for ๐ โฅ 9 and that 2๐โ1 โ 1 โฅ (4/3) ยท 2๐โ2
for ๐ โฅ 3 (note that ๐ โฅ 2 log(50๐ก/๐) โฅ 2 log 100 > 13), in the second inequality we used
๐ โฅ 2 log(50๐ก/๐), and in the third inequality we used 2 ๐ โค 8๐ and ๐ก โฅ 1.
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 16
S UBLINEAR -T IME C OMPUTATION IN THE P RESENCE OF O NLINE E RASURES
Since the round is special, at least a 2โ๐ fraction of the sums that can be queried in Step 8 are
violating. Thus, the fraction of the sums that are violating and nonerased before each iteration
of Steps 8-9 in this round is at least 2โ๐ โ 2โ๐โ1 = 2โ๐โ1 .
Then, each iteration of Steps 8-9 rejects with probability at least 2โ๐โ1 . Since there are 4 ยท 2 ๐
iterations with independently chosen sums, the probability that the special round accepts is at
most
๐
(1 โ 2โ๐โ1 )4ยท2 โค eโ2 โค 1/6.
That is, the probability that Algorithm 1 rejects in the special round is at least 5/6. Since the
special round exists with probability at least 45 , Algorithm 1 rejects with probability at least
5 ยท 6 = 3.
4 5 2
3 An online-erasure-resilient linearity tester with ๐(๐ก/๐) queries
In this section, we present our online-erasure-resilient linearity tester with query complexity
๐(๐ก/๐) (Algorithm 2) and prove Theorem 3.1 below. Theorem 3.1 together with Theorem 2.1
implies Theorem 1.1.
Theorem 3.1. There exist a constant ๐ 0 โ (0, 1) and a 1-sided error, nonadaptive, ๐ก-online-erasure-
resilient ๐-tester for linearity of functions ๐ : {0, 1} ๐ โ {0, 1} that works for ๐ก โค ๐ 0 ยท ๐ ยท 2๐/4 and makes
๐( ๐๐ก ) queries.
Algorithm 2 An Online-Erasure-Resilient Linearity Tester
Input: ๐ โ (0, 12 ), erasure budget ๐ก โ โ , access to function ๐ : {0, 1} ๐ โ {0, 1} via a ๐ก-online-
erasure oracle.
1: Let ๐ = 88 and ๐ = ๐๐ก ๐.
2: for all ๐ โ [๐]:
3: Sample ๐ฅ ๐ โผ {0, 1} ๐ and query ๐ at ๐ฅ ๐ .
4: repeat 24๐ times:
5: Sample a uniform (๐, ๐) such that ๐, ๐ โ [๐] and ๐ < ๐, then query ๐ at ๐ฅ ๐ โ ๐ฅ ๐ .
6: Reject if ๐ฅ ๐ , ๐ฅ ๐ , and ๐ฅ ๐ โ ๐ฅ ๐ are nonerased and ๐ (๐ฅ ๐ ) + ๐ (๐ฅ ๐ ) โ ๐ (๐ฅ ๐ โ ๐ฅ ๐ ).
7: Accept.
In the analysis of Algorithm 2, we let ๐ฅ ๐ , for all ๐ โ [๐], be random variables denoting
the points queried in Step 3. Recall that a pair (๐ฅ, ๐ฆ) of domain points violates linearity if
๐ (๐ฅ) + ๐ (๐ฆ) โ ๐ (๐ฅ โ ๐ฆ). The proof of Theorem 3.1 crucially relies on the following lemma about
the concentration of pairs violating linearity.
Lemma 3.2. Suppose ๐ is ๐-far from linear and ๐ = ๐๐ก๐ . Let ๐ denote the number of pairs (๐, ๐) โ [๐]2
๐ ๐
such that ๐ < ๐ and (๐ฅ ๐ , ๐ฅ ๐ ) violates linearity. Then Pr[๐ โค 4 ยท 2 ] โค 0.25.
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 17
I DEN K ALEMAJ , S OFYA R ASKHODNIKOVA , AND N ITHIN VARMA
We prove Lemma 3.2 in Section 3.1. In the rest of this section, we first prove an auxiliary
lemma (Lemma 3.3) and then use Lemmas 3.2 and 3.3 to prove Theorem 3.1.
We say a query ๐ข โ {0, 1} ๐ is successfully obtained if it is nonerased right before it is queried,
i.e., the tester obtains ๐ (๐ข) as opposed to the symbol โฅ.
Lemma 3.3. Let ๐บ1 be the (good) event that all 2๐ sums ๐ฅ ๐ โ ๐ฅ ๐ of points queried in Step 3 of Algorithm 2
are distinct, and ๐บ2 be the (good) event that all ๐ points ๐ฅ ๐ queried in Step 3 are successfully obtained.
Then Pr[๐บ1 โช ๐บ2 ] โค 0.05 for all adversarial strategies.
Proof. First, we analyze event ๐บ1 . Consider points ๐ฅ ๐ , ๐ฅ ๐ , ๐ฅ ๐ , ๐ฅโ โผ {0, 1} ๐ , where {๐, ๐} โ {๐, โ }.
Since these points are distributed uniformly and independently, so are the sums ๐ฅ ๐ โ ๐ฅ ๐ and
๐ฅ ๐ โ ๐ฅโ . The probability that two uniformly and independently sampled points ๐ฅ, ๐ฆ โผ {0, 1} ๐
๐4
are identical is 21๐ . Therefore, by a union bound over all pairs of sums, Pr[๐บ1 ] โค 2๐ ยท 21๐ โค 4ยท2๐ .
2
To analyze ๐บ2 , fix an arbitrary adversarial strategy. In Steps 2-3, the algorithm makes at
most ๐ queries. Hence the oracle erases at most ๐๐ก points from {0, 1} ๐ . Since each point ๐ฅ ๐ is
sampled uniformly from {0, 1} ๐ ,
๐๐ก
Pr [๐ฅ ๐ is erased when queried] โค .
๐ฅ ๐ โผ{0,1} ๐ 2๐
๐2 ๐ก
By a union bound over the ๐ points sampled in Step 3, we get Pr[๐บ2 ] โค 2๐ . We substitute ๐ = ๐๐ก๐
and get
๐4 ๐2๐ก ๐4 ๐4๐ก4
Pr[๐บ1 โช ๐บ2 ] โค ๐
+ ๐
โค ๐
= โค ๐ 4 ๐04 โค 0.05,
4ยท2 2 2 ๐4 ยท 2 ๐
since ๐ก โค ๐ 0 ยท ๐ ยท 2๐/4 , as stated in Theorem 3.1, and assuming ๐ 0 is sufficiently small.
Proof of Theorem 3.1. The query complexity of Algorithm 2 is evident from its description. Clearly,
Algorithm 2 is nonadaptive and accepts if ๐ is linear. Suppose now that ๐ is ๐-far from linear
and fix an arbitrary adversarial strategy. We show that Algorithm 2 rejects with probability at
least 23 .
We call a sum ๐ฅ ๐ โ ๐ฅ ๐ queried in Step 5 violating if the pair (๐ฅ ๐ , ๐ฅ ๐ ) violates linearity. For
Algorithm 2 to reject, it must sample ๐, ๐ โ [๐] such that ๐ฅ ๐ , ๐ฅ ๐ , and ๐ฅ ๐ โ ๐ฅ ๐ are successfully
obtained and ๐ฅ ๐ โ ๐ฅ ๐ is a violating sum. Let ๐ธ ๐ , for all ๐ โ [24/๐], be the event that in iteration ๐
of Step 4, the algorithm successfully obtains a violating sum. Let ๐ธ = ๐โ[24/๐] ๐ธ ๐ . We define
ร
the following good event concerning the execution of the for loop: ๐บ = ๐บ1 โฉ ๐บ2 โฉ ๐บ3 , where ๐บ1
and ๐บ 2 are as defined in Lemma 3.3, and ๐บ3 is the event that ๐, defined in Lemma 3.2, is at least
๐ ๐
4 ยท 2 . By a union bound and Lemmas 3.2 and 3.3, we know that Pr[๐บ] โฅ 0.7. Therefore, the
probability that Algorithm 2 rejects is at least
Pr[๐ธ โฉ ๐บ] = Pr[๐บ] ยท Pr[๐ธ|๐บ] โฅ 0.7 ยท Pr[๐ธ|๐บ].
Suppose that ๐บ occurs for the execution of the for loop. Since ๐บ2 occurred, all ๐ points
queried in Step 3 of Algorithm 2 were successfully obtained. So, the algorithm will reject as
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 18
S UBLINEAR -T IME C OMPUTATION IN THE P RESENCE OF O NLINE E RASURES
soon as it successfully obtains a violating sum. Since ๐บ1 occurred, there are at least 2๐ distinct
sums that can be queried in Step 5. Since ๐บ3 occurred, at least 4๐ ยท 2๐ of them are violating.
The total number of erasures the adversary makes over the course of the entire execution is at
most 2๐๐ก, since Algorithm 2 queries at most 2๐ points. Therefore, the fraction of sums that are
nonerased and violating before each iteration of Step 5 is at least
๐ 2๐๐ก ๐ 5๐ก ๐ 5๐ ๐ 5๐ ๐
โ ๐ โฅ โ = โ = โ > .
4 4 ๐ 4 ๐ 4 88 6
2
That is, Pr[๐ธ ๐ |๐บ] > ๐/6 for all ๐ โ [24/๐]. Observe that the indicator for the event ๐ธ ๐ , for every
fixed setting of random coins (of the algorithm and the adversary) used prior to iteration ๐ of
Step 5, is a Bernoulli random variable with the probability parameter equal to the fraction of
sums that are violating and nonerased right before iteration ๐. Since independent random coins
are used in each iteration of Step 5,
ร
๐ธ ๐ | ๐บ < (1 โ ๐/6)24/๐ โค eโ4 .
Pr[๐ธ|๐บ] โค Pr
๐โ[24/๐]
This yields that Pr[๐ธ โฉ ๐บ] > 0.7 ยท (1 โ eโ4 ) > 2/3, completing the proof of the theorem.
3.1 Concentration of pairs that violate linearity
In this section, we prove Lemma 3.2 on the concentration of pairs that violate linearity. The
proof relies on Claim 3.4 that gives upper bounds on the fraction of pairs (๐ฅ, ๐ฆ) โ ({0, 1} ๐ )2
that violate linearity and on the fraction of triples (๐ฅ, ๐ฆ, ๐ง) โ {0, 1} ๐ร3 such that (๐ฅ, ๐ฆ) and (๐ฅ, ๐ง)
violate linearity. The upper bounds are stated as a function of the distance to linearity. The
distance of a function ๐ to linearity, denoted ๐ ๐ , is the minimum over all linear functions ๐ over
the same domain as ๐ of Pr๐ฅ [ ๐ (๐ฅ) โ ๐(๐ฅ)].
We remark that a tighter upper bound than (3.1) in Claim 3.4 is shown in [8, Lemma 3.2].
Since we only need a looser upper bound, we provide a proof for completeness.
Claim 3.4. For all ๐ : {0, 1} ๐ โ {0, 1}, the following hold:
Pr [(๐ฅ, ๐ฆ) violates linearity] โค 3๐ ๐ ; (3.1)
๐ฅ,๐ฆโผ{0,1} ๐
Pr [(๐ฅ, ๐ฆ) and (๐ฅ, ๐ง) violate linearity] โค ๐ ๐ + 4๐2๐ . (3.2)
๐ฅ,๐ฆ,๐งโผ{0,1} ๐
Proof. Let ๐ be the closest linear function to ๐ . Let ๐ โ {0, 1} ๐ be the set of points on which ๐
and ๐ differ, i.e., ๐ = {๐ฅ โ {0, 1} ๐ | ๐ (๐ฅ) โ ๐(๐ฅ)}. Then |๐| = ๐ ๐ ยท 2๐ .
For a pair (๐ฅ, ๐ฆ) to violate linearity, at least one of ๐ฅ, ๐ฆ, and ๐ฅ โ ๐ฆ must be in ๐. By a union
bound,
Pr [(๐ฅ, ๐ฆ) violates linearity for ๐ ] โค Pr [๐ฅ โ ๐ โจ ๐ฆ โ ๐ โจ ๐ฅ โ ๐ฆ โ ๐]
๐ฅ,๐ฆโผ{0,1} ๐ ๐ฅ,๐ฆโผ{0,1} ๐
โค3 Pr [๐ฅ โ ๐] = 3๐ ๐ ,
๐ฅโผ{0,1} ๐
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 19
I DEN K ALEMAJ , S OFYA R ASKHODNIKOVA , AND N ITHIN VARMA
completing the proof of (3.1).
To prove (3.2), let ๐ธ ๐ฅ,๐ฆ,๐ง be the event that (๐ฅ, ๐ฆ) and (๐ฅ, ๐ง) violate linearity. By the law of total
probability,
Pr [๐ธ ๐ฅ,๐ฆ,๐ง ]
๐ฅ,๐ฆ,๐งโผ{0,1} ๐
= Pr[๐ธ ๐ฅ,๐ฆ,๐ง | ๐ฅ โ ๐] Pr[๐ฅ โ ๐] + Pr[๐ธ ๐ฅ,๐ฆ,๐ง | ๐ฅ โ ๐] Pr[๐ฅ โ ๐]
โค 1 ยท ๐ ๐ + Pr[๐ธ ๐ฅ,๐ฆ,๐ง | ๐ฅ โ ๐]
โค ๐ ๐ + Pr[(๐ฆ, ๐ง โ ๐) โจ (๐ฅ โ ๐ฆ, ๐ง โ ๐) โจ (๐ฆ, ๐ฅ โ ๐ง โ ๐) โจ (๐ฅ โ ๐ฆ, ๐ฅ โ ๐ง โ ๐) | ๐ฅ โ ๐]
โค ๐ ๐ + 4 Pr[๐ฆ, ๐ง โ ๐ | ๐ฅ โ ๐] = ๐ ๐ + 4๐2๐ ,
where, in the last line, we used symmetry and a union bound, and then independence of ๐ฅ, ๐ฆ,
and ๐ง.
Proof of Lemma 3.2. We prove the lemma by applying Chebyshevโs inequality to ๐. For all
๐, ๐ โ [๐], where ๐ < ๐, let ๐๐,๐ be the indicator for the event that (๐ฅ ๐ , ๐ฅ ๐ ) violates linearity. Then
๐ = ๐<๐โ[๐] ๐๐,๐ .
ร
First, we obtain a lower bound on ๐ผ[๐]. By linearity of expectation and symmetry,
๐ ๐
ร
๐ผ[๐] = ๐ผ[๐๐,๐ ] = ยท Pr [(๐ฅ ๐ , ๐ฅ ๐ ) violates linearity] โฅ ๐๐ ,
2 ๐ฅ ๐ ,๐ฅ ๐ โผ{0,1} ๐ 2
๐<๐โ[๐]
where the inequality is due to [8, Theorem 1.2].
Next, we obtain an upper bound on Var[๐]. We have
ร ร
Var[๐] = Var[๐๐,๐ ] + Cov[๐๐,๐ ๐๐,๐ ].
๐<๐ ๐<๐,๐<๐
{๐,๐}โ {๐,โ }
By (3.1), we get Var[๐๐,๐ ] โค ๐ผ[๐๐,๐
2
] = ๐ผ[๐๐,๐ ] โค 3๐ ๐ . Therefore,
๐
ร
Var[๐๐,๐ ] โค 3 ๐๐ . (3.3)
2
๐<๐
When {๐, ๐} โฉ {๐, โ } = โ
, the random variables ๐๐,๐ and ๐๐,โ are independent, and thus
Cov[๐๐,๐ ๐๐,๐ ] = 0. Consider the case when |{๐, ๐} โฉ {๐, โ }| = 1. Suppose that ๐ = ๐. Then
Cov[๐๐,๐ ๐๐,โ ] = ๐ผ[๐๐,๐ ๐๐,โ ] โ ๐ผ[๐๐,๐ ]๐ผ[๐๐,โ ] โค ๐ ๐ + 4๐2๐ โ ๐2๐ = ๐ ๐ + 3๐2๐ ,
where the inequality follows from (3.2) and [8, Theorem 1.2]. By symmetry,
๐ ๐
ร ร
Cov[๐๐,๐ ๐๐,๐ ] = 6 Cov[๐๐,๐ ๐๐,๐ ] โค 6 (๐ ๐ + 3๐2๐ ) โค 15 ๐๐ , (3.4)
3 3
๐<๐,๐<๐ ๐<๐<โ
{๐,๐}โ {๐,โ }
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 20
S UBLINEAR -T IME C OMPUTATION IN THE P RESENCE OF O NLINE E RASURES
where the last inequality holds since ๐ ๐ โค 12 . Combining (3.3) with (3.4), we get that Var[๐] โค
๐
18 3 ๐ ๐ .
Finally, we use ๐ ๐ โฅ ๐, our lower bound on ๐ผ[๐], and Chebyshevโs inequality:
๐ ๐ ๐ ๐๐
๐ผ[๐]
Pr ๐ โค โค Pr ๐ โค โค Pr ๐ โค
2 4 2 4 4
๐
๐
3 16 Var[๐] 16 ยท 18 3 ๐
โค Pr ๐ โ ๐ผ[๐] โฅ ยท ๐ผ[๐] โค ยท โค ยท
9 ๐ผ[๐] ๐ 2 2
๐๐
4 2 9
2
16 ยท 18 2 ๐โ2 22 22๐ 22 1
= ยท ยท < = โค โค ,
9 3 ๐(๐ โ 1)๐ ๐ ๐ ยท ๐๐ ๐๐ก๐ ๐ ๐๐ก 4
since ๐ = ๐๐ก๐ and ๐ = 88. This completes the proof of Lemma 3.2.
4 A lower bound for online-erasure-resilient linearity testing
In this section, we prove Theorem 1.3 that shows that every ๐ก-online-erasure-resilient ๐-tester for
linearity of functions ๐ : {0, 1} ๐ โ {0, 1} must make more than log2 ๐ก queries.
Proof of Theorem 1.3. The proof is via Yaoโs minimax principle for the online-erasures model
(stated in Theorem 9.1 and Corollary 9.4). Let ๐ + be the uniform distribution over all linear
Boolean functions on {0, 1} ๐ and ๐ โ be the uniform distribution over all Boolean functions
functions on {0, 1} ๐ .
We show that a function ๐ โผ ๐ โ is 14 -far from linear with probability at least 6/7. Let ๐
be a linear function, ๐ โผ ๐ โ , and dist( ๐ , ๐) be the fraction of domain points on which ๐ and
2๐
๐ differ. Then, ๐ผ[dist( ๐ , ๐)] = 12 . By the Hoeffding bound, Pr ๐ โผ๐ โ [dist( ๐ , ๐) โค 14 ] โค eโ 8 . By a
2๐
union bound over the 2๐ linear functions, Pr ๐ โผ๐ โ [ ๐ is 14 -far from linear] โฅ 1 โ 2๐ ยท eโ 8 . For ๐
large enough, this probability is at least 6/7.
We fix the following strategy for a ๐ก-online-erasure oracle ๐ช: after responding to each query,
erase ๐ก sums of the form ๐ฅ, where ๐ is a subset of the queries made so far, choosing the
ร
๐ฅโ๐
subsets ๐ in some fixed order. If at most log2 ๐ก queries are made, the adversary erases all the
sums of queried points.
Let ๐ด be a deterministic algorithm that makes ๐ โค log2 ๐ก queries to the oracle ๐ช. Assume
w.l.o.g. that ๐ด does not repeat queries. We describe two random processes ๐ซ + and ๐ซ โ that
interact with algorithm ๐ด in lieu of oracle ๐ช and provide query answers consistent with a
random function from ๐ + and ๐ โ , respectively. For each query of ๐ด, both processes ๐ซ + and
๐ซ โ return โฅ if the value has been previously erased by ๐ช; otherwise, they return 0 or 1 with
equal probability. Thus, the distribution over query-answer histories when ๐ด interacts with ๐ซ +
is the same as when ๐ด interacts with ๐ซ โ .
Next, we describe how the processes ๐ซ + and ๐ซ โ assign values to the locations of ๐ that
were either not queried by ๐ด or erased when queried, and show that they generate ๐ + and ๐ โ ,
respectively. After ๐ด finishes its queries, ๐ซ โ sets the remaining unassigned locations (including
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 21
I DEN K ALEMAJ , S OFYA R ASKHODNIKOVA , AND N ITHIN VARMA
the erased locations) of the function to be 0 or 1 with equal probability. Clearly, ๐ซ โ generates a
function from the distribution ๐ โ .
To describe ๐ซ + fully, first let ๐ โ {0, 1} ๐ denote the queries of ๐ด that are answered with a
value other than โฅ. Since ๐ โค log2 ๐ก, by our choice of the oracle ๐ช, the sum of any subset of
vectors in ๐ is not contained in ๐. Hence, the vectors in ๐ are linearly independent. Then, ๐ซ +
completes ๐ to a basis ๐ต for {0, 1} ๐ and sets the value of ๐ on all vectors in ๐ต \ ๐ independently
to 0 or 1 with equal probability.
Since ๐ต is a basis, each vector ๐ฆ โ {0, 1} ๐ canรbe expressed as a linear combination of vectors
in ๐ต (with coefficients in {0, 1}), that is, ๐ฆ = ๐ฅโ๐ ๐ฅ for some ๐ โ ๐ต. The process ๐ซ sets
+
๐ (๐ฆ) = ๐ฅโ๐ ๐ (๐ฅ), where addition is mod 2. The function ๐ is linear and agrees with all values
ร
previously assigned by ๐ซ + to the vectors in ๐. Moreover, ๐ is distributed according to ๐ + , since
one can obtain a uniformly random linear function by first specifying a basis for {0, 1} ๐ , and
then setting the value of ๐ to be 0 or 1 with equal probability for each basis vector.
Thus, ๐ซ + generates linear functions, ๐ซ โ generates functions that are 14 -far from linear with
probability at least 67 , and the query-answer histories for any deterministic algorithm ๐ด that
makes at most log2 ๐ก queries and runs against our ๐ก-online-erasure oracle ๐ช are identical under
๐ซ + and ๐ซ โ . Consequently, Corollary 9.4 implies the desired lower bound.
5 An online-erasure-resilient quadraticity tester
In this section, we state our online-erasure-resilient quadraticity tester (Algorithm 3) and prove
Theorem 1.4.
The main idea behind Algorithm 3 and its representation as a two-player game appear in
Section 1.2, accompanied by explanatory figures for the case when ๐ก = 1. We now give a high
level overview of Algorithm 3. For a function ๐ : {0, 1} ๐ โ {0, 1} and ๐ฅ, ๐ฆ, ๐ง โ {0, 1} ๐ , let
ร ร
๐๐ (๐ฅ, ๐ฆ, ๐ง) = ๐ ๐ข ,
โ
โ ๐โ{๐ฅ,๐ฆ,๐ง} ๐ขโ๐
where the first sum is mod 2. We say a triple (๐ฅ, ๐ฆ, ๐ง) violates quadraticity if ๐๐ (๐ฅ, ๐ฆ, ๐ง) = 1.
The tester of Alon et al. samples three vectors ๐ฅ, ๐ฆ, ๐ง โ {0, 1} ๐ uniformly and independently
at random and rejects if (๐ฅ, ๐ฆ, ๐ง) violates quadraticity. Our tester looks for the same kind of
violations as the tester of Alon et al.
The main challenge in the design of our online-erasure-resilient tester is to ensure it can
query all three such points and their sums in the presence of a ๐ก-online-erasure adversary. In
each iteration of the repeat loop of Algorithm 3, the following steps are performed. For each
(โ )
โ โ [๐ก + 1], we first query a reserve of uniformly and independently sampled points ๐ฅ ๐ for
๐ โ [(๐ก + 1)2 (2๐ก + 1)๐ก ]. Next, for each โ โ [๐ก + 1], we query a set of points that we visualize as
being the nodes of a (๐ก + 1)-ary tree of depth ๐ก. There is a one-to-one correspondence between
the nodes of such a tree and vectors of length up to ๐ก + 1 over the alphabet [๐ก + 1]. For ๐ โ [๐ก],
we represent by ๐ฆ(โ ,๐1 ,...,๐๐ ) , the sampled point visualized as a node at depth ๐ in the โ -th tree,
where the ๐๐ โs specify the unique path from the root to that node in the tree. Now, for โ โ [๐ก + 1],
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 22
S UBLINEAR -T IME C OMPUTATION IN THE P RESENCE OF O NLINE E RASURES
and for each node ๐ฆ ๐ in the โ -th tree, where ๐ is shorthand for (โ , ๐1 , . . . , ๐๐ ), we associate with
that node a subset ๐ ๐ of points from the reserve, and query the points ๐ฆ ๐ โ ๐ฅ for each ๐ฅ in ๐ ๐ .
The set ๐ ๐ is a subset of a specified cardinality of the set ๐ ๐ (โ1) , where ๐ ๐ (โ1) is the set associated
with the parent node of ๐ฆ ๐ in the โ -th tree. Finally, the algorithm queries a point ๐ง sampled
uniformly and independently at random from {0, 1} ๐ , and samples a uniformly random leaf ๐ฆ ๐
of a uniformly random tree โ โ [๐ก + 1]. The set ๐ ๐ associated with the leaf ๐ฆ ๐ has, by construction,
๐ก + 1 points in it. All the points in ๐ ๐ , again, by construction, also belong to the sets ๐ ๐0 associated
with the nodes ๐ฆ ๐0 on the path from the root to the leaf ๐ฆ ๐ of the โ -th tree. Our algorithm queries
๐ฆ ๐0 โ ๐ง for all such nodes ๐ฆ ๐0 . It then samples ๐ฅ uniformly at random from ๐ ๐ and queries ๐ฅ โ ๐ง.
Finally, it samples a uniformly random node ๐ฆ ๐0 on the path from the root to the leaf ๐ฆ ๐ and
queries ๐ฅ โ ๐ฆ ๐0 โ ๐ง. Observe that, by design, the point ๐ฅ โ ๐ฆ ๐0 has already been queried in an
earlier step. The algorithm rejects if all the points involved in the sum ๐๐ (๐ฅ, ๐ฆ ๐0 , ๐ง) are nonerased
and the triple (๐ฅ, ๐ฆ ๐0 , ๐ง) violates quadraticity.
Algorithm 3 uses the following notation. For a vector ๐ = (โ , ๐1 , . . . , ๐๐ ), where ๐ โ [0, ๐ก]
and โ , ๐1 , . . . , ๐๐ก โ [๐ก + 1], we use the convention that ๐ = (โ ) for ๐ = 0. For ๐ โ [0, ๐], let
๐ (๐) = (โ , ๐1 , . . . , ๐ ๐ ) be the vector containing the first ๐ + 1 entries of ๐. Finally, let ๐ (โ1) be the
vector ๐ with its last entry removed. If ๐ = (โ ), then ๐ (โ1) is the empty vector โ
.
Algorithm 3 A ๐ก-Online-Erasure-Resilient Quadraticity Tester
Input: ๐ โ (0, 1), access to function ๐ : {0, 1} ๐ โ {0, 1} via a ๐ก-online-erasure oracle.
(๐ก+1)(๐ก+1) โ1
1: Let ๐ผ = (๐ก + 1)2 (2๐ก + 1)๐ก , ๐ฝ = , and ๐ผ = min 2๐ , (18ยท๐ผ๐ฝ(๐ก+1)) ๐ผ๐ฝ(๐ก+1) .
7
๐ก
2: repeat 4๐ ๐ก /๐ผ times: โฒ ๐ ๐ก is a constant from Lemma 5.4 that depends only on ๐ก .
3: for all โ โ [๐ก + 1]:
(โ ) (โ ) (โ ) (โ )
4: Query ๐ at independent ๐ฅ 1 , . . . , ๐ฅ ๐ผ โผ {0, 1} ๐ , and let ๐โ
= {๐ฅ 1 , . . . , ๐ฅ ๐ผ }.
5: for all integer ๐ โ [0, ๐ก]:
6: for all (๐1 , ๐2 , . . . , ๐๐ ) โ [๐ก + 1]๐ : โฒ When ๐ = 0, the loop is run once.
7: Let ๐ = (โ , ๐1 , . . . , ๐๐ ) and query ๐ at ๐ฆ ๐ โผ {0, 1} ๐ . โฒ ๐ = (โ ) for ๐ = 0.
8: Let ๐ ๐ be a uniformly random subset of ๐ ๐ (โ1) of size (๐ก + 1)(2๐ก + 1)๐กโ๐ .
9: Query ๐ฅ โ ๐ฆ ๐ for all ๐ฅ โ ๐ ๐ .
10: Remove ๐ ๐ from ๐ ๐ (โ1) .
11: Sample ๐ง โผ {0, 1} ๐ and query ๐ at ๐ง.
12: Sample ๐ = (โ , ๐1 , . . . , ๐๐ก ) โผ [๐ก + 1](๐ก+1) and query ๐ at ๐ฆ ๐ (๐) โ ๐ง for all ๐ โ [0, ๐ก].
(โ ) (โ ) (โ ) (โ )
13: Suppose ๐ ๐ = {๐ฅ 1 , ๐ฅ2 , . . . , ๐ฅ ๐ก+1 }. Sample ๐ โผ [๐ก + 1] and query ๐ at ๐ฅ ๐ โ ๐ง.
(โ )
14: Sample integer ๐ โผ [0, ๐ก] and query ๐ at ๐ฅ ๐ โ ๐ฆ ๐ (๐) โ ๐ง.
(โ )
15: Reject if ๐๐ (๐ฅ ๐ , ๐ฆ ๐ (๐) , ๐ง) = 1. โฒ All points needed for computing ๐๐ are nonerased.
16: Accept.
Proof of Theorem 1.4. If ๐ is quadratic, then Algorithm 3 always accepts. Suppose that ๐ is
๐-far from quadratic. Fix an adversarial strategy and a round of Algorithm 3. We show that
Algorithm 3 rejects with probability ฮฉ(๐) in this round.
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 23
I DEN K ALEMAJ , S OFYA R ASKHODNIKOVA , AND N ITHIN VARMA
(โ )
Observe that Algorithm 3 makes queries of three types: singletons (of the form ๐ฅ ๐ , ๐ฆ ๐ (๐) , and
(โ ) (โ ) (โ )
๐ง), doubles (of the form ๐ฅ ๐ โ ๐ฆ ๐ (๐) ,๐ฅ ๐ โ ๐ง, and ๐ฆ ๐ (๐) โ ๐ง), and triples (of the form ๐ฅ ๐ โ ๐ฆ ๐ (๐) โ ๐ง),
(โ )
where ๐ โ [๐ผ], ๐ = (โ , ๐1 , . . . , ๐๐ก ) โ [๐ก + 1](๐ก+1) , ๐ โ [0, ๐ก]. We call points of the form ๐ฅ ๐ โ ๐ฆ ๐ (๐) ,
(โ ) (โ )
๐ฅ ๐ โ ๐ง, and ๐ฆ ๐ (๐) โ ๐ง double decoys, and points of the form ๐ฅ ๐ โ ๐ฆ ๐ (๐) โ ๐ง triple decoys. We refer to
double and triple decoys simply as decoys. Only some of the decoys become actual queries.
Let ๐ข denote the good event that, for the fixed round, all of the following hold:
โข all singleton queries are successfully obtained;
(โ )
โข all double decoys of the form ๐ฅ ๐ โ ๐ฆ ๐ (๐) are nonerased right before ๐ฆ ๐ (๐) is queried;
(โ )
โข all double and triple decoys involving ๐ง (as well as ๐ฅ ๐ and/or ๐ฆ ๐ (๐) ) are nonerased right
before ๐ง is queried.
To lower bound the rejection probability of the algorithm, we consider the event that all
(โ )
triples of the form (๐ฅ ๐ , ๐ฆ ๐ (๐) , ๐ง), where ๐ โ [๐ผ], ๐ = (โ , ๐1 , . . . , ๐๐ก ) โ [๐ก + 1](๐ก+1) , ๐ โ [0, ๐ก], violate
quadraticity, and all queries in the round are successfully obtained.
(โ )
Definition 5.1 (Witness). The singleton queries form a witness if ๐๐ (๐ฅ ๐ , ๐ฆ ๐ (๐) , ๐ง) = 1 for all
๐ โ [๐ผ], ๐ = (โ , ๐1 , . . . , ๐๐ก ) โ [๐ก + 1](๐ก+1) , ๐ โ [0, ๐ก], and, in addition, all singletons and all decoys
are distinct.
Let ๐ be the event that the singleton queries form a witness. Let ๐ผ be as defined in Step 1.
Lemma 5.2 (Probability of successful singleton queries). If ๐ : {0, 1} ๐ โ {0, 1} is ๐-far from being
quadratic, then Pr[๐ โฉ ๐ข] โฅ ๐ผ/2.
In other words, Lemma 5.2 shows that for every adversarial strategy, with probability at least
๐ผ
2 , the tester successfully obtains singleton queries that form a witness and, in addition, right
before each singleton is queried, the decoys involving that singleton are nonerased. The proof
of Lemma 5.2 (in Section 5.1) relies on the following key structural result about the fraction of
large structures where all triples of a certain form violate quadraticity.
Lemma 5.3 (Probability of singletons forming a violation structure). Let ๐ผ, ๐ฝ, ๐ก โ โ . Suppose
(โ ) (โ )
๐ : {0, 1} ๐ โ {0, 1} is ๐-far from being quadratic. For points ๐ฅ ๐ , ๐ฆ ๐ , ๐ง โผ {0, 1} ๐ , where (๐, ๐, โ ) โ
[๐ผ] ร [๐ฝ] ร [๐ก + 1],
ร
(โ ) (โ )
Pr [๐๐ (๐ฅ ๐ , ๐ฆ ๐ , ๐ง) = 1] โฅ ๐ผ, (5.1)
๐โ[๐ผ],๐โ[๐ฝ],โ โ[๐ก+1]
where ๐ผ = min 2๐ , (18ยท๐ผ๐ฝ(๐ก+1)) ๐ผ๐ฝ(๐ก+1) .
7
We prove Lemma 5.3 in Section 5.2, building on a result of [2]. To prove Lemma 5.2, we use
ร๐ก (๐ก+1) โ1
Lemma 5.3 with ๐ผ = (๐ก + 1)2 (2๐ก + 1)๐ก and ๐ฝ = ๐=0 (๐ก + 1)
๐ = (๐ก+1)
๐ก , which is the number of
nodes in each tree.
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 24
S UBLINEAR -T IME C OMPUTATION IN THE P RESENCE OF O NLINE E RASURES
Next, in Lemma 5.4, we show that the probability of successfully obtaining all double and
triple queries in the round, given the event ๐ โฉ ๐ข, depends only on ๐ก. The proof of Lemma 5.4
appears in Section 5.3.
Lemma 5.4 (Probability of all double and triple queries being nonerased). The probability that all
queries made in one round of Algorithm 3 are successfully obtained, conditioned on the event ๐ โฉ ๐ข, is
at least 1/๐ ๐ก , where ๐ ๐ก depends only on ๐ก.
Let ๐ป denote the event that all queries in the round are successfully obtained, and recall
that ๐ is the event that the singleton queries form a witness. The probability that Algorithm 3
rejects in the given round is at least Pr[๐ โฉ ๐ป]. Note that
Pr[๐ โฉ ๐ป] โฅ Pr[๐ โฉ ๐ป โฉ ๐ข] = Pr[๐ป | ๐ โฉ ๐ข] Pr[๐ โฉ ๐ข].
By Lemma 5.2 and Lemma 5.4, we have that Algorithm 3 rejects with probability at least ๐1๐ก ยท ๐ผ2
for a fixed round. Thus, after 4๐๐ผ๐ก rounds, Algorithm 3 rejects with probability at least 23 .
5.1 Proof of Lemma 5.2
In this section, we prove Lemma 5.2 that bounds from below the probability that the singleton
queries are successfully obtained and form a witness, and, in addition, right before each singleton
is queried, the decoys involving that singleton are nonerased. We show that if the fraction of
large violation structures is at least ๐ผ (Lemma 5.3), then, despite the adversarial erasures, the
probability of successful singleton queries, as described above, is at least ๐ผ/2.
Proof of Lemma 5.2. The key idea of the proof is to keep track of active witnesses during the
execution of the round. To simplify notation, let ๐พ = (๐ผ + ๐ฝ)(๐ก + 1) + 1 and denote by ๐ข1 , . . . , ๐ข๐พ
the singleton queries made by Algorithm 3 in the given round.
Definition 5.5 (Active witness). For ๐ โ [๐พ], let ๐ข1 , . . . , ๐ข๐ denote the singleton queries made
by Algorithm 3 up until a given timepoint of the fixed round. We say a witness (๐ฃ 1 , . . . , ๐ฃ ๐พ ) โ
({0, 1} ๐ )๐พ is ๐-active if
1. The first ๐ entries of the tuple are equal to ๐ข1 , ๐ข2 , . . . , ๐ข๐ .
2. All decoys involving ๐ข ๐ , where ๐ โค ๐, were nonerased right before ๐ข ๐ was queried.
Furthermore, let ๐ด ๐ be a random variable denoting the number of active witnesses right after
the ๐-th singleton query, and let ๐ต ๐ denote the number of active witnesses right before the ๐-th
singleton query. Let ๐ต1 denote the number of witnesses at the beginning of the round, such that all
singletons and decoys for the witness are nonerased. Note that Pr[๐ โฉ ๐ข] = Pr[๐ด๐พ = 1] = ๐ผ[๐ด๐พ ].
To lower bound ๐ผ[๐ด๐พ ], we first show a lower bound on ๐ต1 , obtained in turn by a lower bound
on the total fraction of witnesses. We then bound the difference between ๐ด ๐ and ๐ต ๐+1 and show
a relationship between ๐ผ[๐ด ๐ ] and ๐ผ[๐ต ๐ ] for general ๐. All expectations in this proof are over the
choice of singletons ๐ข1 , . . . , ๐ข๐พ โผ {0, 1} ๐ .
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 25
I DEN K ALEMAJ , S OFYA R ASKHODNIKOVA , AND N ITHIN VARMA
Claim 5.6. Let ๐ผ be as defined in Lemma 5.3. If ๐ is ๐-far from being quadratic then
7๐ผ
Pr [(๐ข1 , . . . , ๐ข๐พ ) is a witness] โฅ .
๐ข1 ,...,๐ข๐พ โผ{0,1} ๐ 8
Proof. The probability that the event of Lemma 5.3 is true for the singleton queries ๐ข1 , . . . , ๐ข๐พ is at
least ๐ผ. Let ๐ denote the set of all singletons and decoys associated with the ๐พ-tuple (๐ข1 , . . . , ๐ข๐พ ).
The number of triple decoys associated with the ๐พ-tuple is at most ๐ผ๐ฝ(๐ก + 1), whereas the number
of double decoys associated with the ๐พ-tuple is at most ๐ผ(๐ฝ + 1)(๐ก + 1). Therefore, |๐| โค 3๐ผ๐ฝ(๐ก + 1).
Any two elements in ๐ are uniformly and independently distributed. Thus, the probability
that two elements in ๐ are identical is 21๐ . By a union bound over all pairs of elements in ๐, the
probability that not all elements in ๐ are distinct is at most |๐|
2
2๐
. For ๐ large enough, we have
|๐| 2
2๐
โค ๐ผ8 . Hence, with probability at least ๐ผ โ ๐ผ8 = 7๐ผ
8 , the singleton queries ๐ข1 , . . . , ๐ข๐พ form a
witness.
Claim 5.7. For all adversarial strategies, ๐ต1 โฅ 3๐ผ ๐พ๐
4 ยท2 .
Proof. Recall that ๐ต1 counts the number of witnesses at the beginning of the round, such that all
singletons and decoys for the witness are nonerased. Algorithm 3 makes at most |๐| queries in
each round, so it makes at most 4๐๐ผ๐ก |๐| queries in total. Therefore, the oracle can erase at most
4๐กยท|๐|ยท๐ ๐ก
๐ผ points from {0, 1} ๐ . Each erasure can deactivate at most |๐| ยท 2(๐พโ1)๐ witnesses, since the
point erased could be any one of the |๐| singletons and decoys associated with the witness. By
๐พ๐ โ 4๐กยท|๐| ยท๐ ๐ก ยท 2(๐พโ1)๐ . Since |๐| โค 3๐ผ๐ฝ(๐ก + 1), for ๐ large enough,
2
Claim 5.6, we obtain ๐ต1 โฅ 7๐ผ
8 ยท2 ๐ผ
we have 4๐กยท|๐|๐ผ ยท๐๐ก ยท 2(๐พโ1)๐ โค ๐ผ8 ยท 2๐พ๐ . Therefore, ๐ต1 โฅ 3๐ผ ๐พ๐
2
4 ยท2 .
Claim 5.8. For all ๐ โ [๐พ โ 1] and all adversarial strategies,
๐ด ๐ โ ๐ต ๐+1 โค (๐ก + 1)2 (2๐ก + 1)๐ก ยท |๐| ยท 2(๐พโ1โ๐)๐ .
Proof. Observe that Algorithm 3 makes at most (๐ก + 1)(2๐ก + 1)๐ก decoy queries between any two
singleton queries (this is the number of double queries made in Step 9 for ๐ = 0). Therefore,
in the period right after the ๐-th singleton query and before the (๐ + 1)-st singleton query, the
oracle can perform at most ((๐ก + 1)(2๐ก + 1)๐ก + 1) ยท ๐ก โค (๐ก + 1)2 (2๐ก + 1)๐ก erasures. Let ๐ข1 , ๐ข2 , . . . , ๐ข๐
be the first ๐ singleton queries of the algorithm. For each erasure, the oracle can deactivate
at most |๐| ยท 2(๐พโ1โ๐)๐ witnesses whose first ๐ entries are ๐ข1 , ๐ข2 , . . . , ๐ข๐ , by erasing one of the
remaining singletons or decoys. Therefore, the number of active witnesses between right after
the ๐-th singleton query and right before the (๐ + 1)-st singleton query can decrease by at most
(๐ก + 1)2 (2๐ก + 1)๐ก ยท |๐| ยท 2(๐พโ1โ๐)๐ .
Claim 5.9. For all ๐ โ [๐พ], it holds that ๐ผ[๐ด ๐ ] = 21๐ ๐ผ[๐ต ๐ ].
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 26
S UBLINEAR -T IME C OMPUTATION IN THE P RESENCE OF O NLINE E RASURES
Proof. For ๐ฃ โ {0, 1} ๐ , let ๐ต ๐,๐ฃ denote the number of witnesses that are active right before the
๐-th singleton query and whose ๐-th entry is equal to ๐ฃ. Then, ๐ต ๐ = ๐ฃโ{0,1} ๐ ๐ต ๐,๐ฃ . Let 1(๐ฃ) be the
ร
indicator random variable for the event that the ๐-th singleton query is equal to ๐ฃ. Then,
h ร i h ร i 1
๐ผ[๐ด ๐ ] = ๐ผ ๐ต ๐,๐ฃ 1(๐ฃ) = ๐ผ[1(๐ฃ)]๐ผ ๐ต ๐,๐ฃ = ๐ผ[๐ต ๐ ] .
2๐
๐ฃโ{0,1} ๐ ๐ฃโ{0,1} ๐
We combine the claims above to complete the proof of the lemma. By Claim 5.9,
1 1 1 1
๐ผ[๐ด๐พ ] = ๐
๐ผ[๐ต๐พ ] = ๐ ๐ผ[๐ด๐พโ1 + ๐ต๐พ โ ๐ด๐พโ1 ] = ๐ ๐ผ[๐ด๐พโ1 ] โ ๐ ๐ผ[๐ด๐พโ1 โ ๐ต๐พ ]
2 2 2 2
๐พโ1
ร ๐ผ[๐ด โ ๐ต ]
1 1 1 ๐ ๐+1
= ๐ผ[๐ต ๐พโ1 ] โ ๐ผ[๐ด ๐พโ1 โ ๐ต ๐พ ] = ยท ยท ยท = ๐ผ [๐ต ] โ .
2๐ 2๐พ๐
1 (๐พโ๐)๐
22๐ ๐=1
2
By Claim 5.7,
1 3๐ผ
๐พ๐
๐ผ[๐ต1 ] โฅ .
2 4
In addition, Claim 5.8 yields that
๐พโ1 ๐พโ1
ร ๐ผ[๐ด โ ๐ต
๐ ๐+1 ]
ร (๐ก + 1)2 (2๐ก + 1)๐ก ยท |๐| ยท 2(๐พโ1โ๐)๐
โค
2 (๐พโ๐)๐ 2(๐พโ๐)๐
๐=1 ๐=1
๐พ ยท (๐ก + 1)2 (2๐ก + 1)๐ก ยท |๐| ๐ผ
โค ๐
โค ,
2 4
where the last inequality holds for large enough ๐. We obtain that
3๐ผ ๐ผ ๐ผ
Pr[๐ โฉ ๐ข] = ๐ผ[๐ด๐พ ] โฅ โ = .
4 4 2
5.2 Proof of Lemma 5.3
In this section, we prove Lemma 5.3 on the fraction of large violation structures for which all
(โ ) (โ )
triples (๐ฅ ๐ , ๐ฆ ๐ , ๐ง), where (๐, ๐, โ ) โ [๐ผ] ร [๐ฝ] ร [๐ก + 1], violate quadraticity. Our proof builds on a
result of [2].
Proof of Lemma 5.3. Let ๐ denote the fraction of violating triples for ๐ , i.e.,
๐ := Pr [๐๐ (๐ฅ, ๐ฆ, ๐ง) = 1].
๐ฅ,๐ฆ,๐งโผ{0,1} ๐
The distance of ๐ to quadraticity, denoted by ๐ ๐ , is the minimum of Pr๐ฅ [ ๐ (๐ฅ) โ ๐(๐ฅ)] over all
quadratic functions ๐ over the same domain as ๐ . Using this notation, we state a result from [2]
for the special case of quadraticity.
Claim 5.10 (Theorem 1 of [2]). For all ๐ , we have ๐ โฅ min( 73 ๐ ๐ , 40
1
).
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 27
I DEN K ALEMAJ , S OFYA R ASKHODNIKOVA , AND N ITHIN VARMA
(โ ) (โ )
Let ๐0 denote the left-hand side of (5.1), that is, the probability that for ๐ฅ ๐ , ๐ฆ ๐ , ๐ง โผ {0, 1} ๐ ,
(โ ) (โ )
all triples (๐ฅ ๐ , ๐ฆ ๐ , ๐ง) are violating, where (๐, ๐, โ ) โ [๐ผ] ร [๐ฝ] ร [๐ก + 1]. Claim 5.11 lower bounds
๐0 in terms of ๐ for all values of ๐ ๐ . Claim 5.13 lower bounds ๐0 for small values of ๐ ๐ . We
combine these results and use Claim 5.10 to conclude the proof of the lemma.
(โ ) (โ )
Claim 5.11. For all ๐ and points ๐ฅ ๐ , ๐ฆ ๐ , ๐ง โผ {0, 1} ๐ , where ๐ โ [๐ผ], ๐ โ [๐ฝ], โ โ [๐ก + 1], it holds that
h ร i
[๐๐ (๐ฅ ๐ , ๐ฆ ๐ , ๐ง) = 1] โฅ ๐ ๐ผ๐ฝ(๐ก+1) .
(โ ) (โ )
Pr
๐โ[๐ผ],๐โ[๐ฝ],โ โ[๐ก+1]
Proof. The proof uses the Hรถlderโs inequality as its key ingredient.
Claim 5.12 (Hรถlderโs inequality). Let ๐, ๐ โฅ 1 such that ๐1 + 1๐ = 1. For all vectors (๐ 1 , . . . , ๐ ๐ ),
(๐1 , . . . , ๐ ๐ ) โ โ ๐ ,
ร ร 1/๐ ร 1/๐
๐ ๐
|๐ ๐ ๐ ๐ | โค |๐ ๐ | |๐ ๐ | .
๐โ[๐] ๐โ[๐] ๐โ[๐]
(โ ) (โ ) (โ ) (โ ) (โ )
For ๐ฅ ๐ , ๐ฆ ๐ , ๐ง โผ {0, 1} ๐ , let ๐๐๐ be the event ๐๐ (๐ฅ ๐ , ๐ฆ ๐ , ๐ง) = 1. Then
h ร i ร h ร i
(โ ) (โ )
Pr ๐๐๐ = Pr ๐๐๐ | ๐ง = ๐ข Pr[๐ง = ๐ข]
๐โ[๐ผ],๐โ[๐ฝ],โ โ[๐ก+1] ๐ขโ{0,1} ๐ ๐โ[๐ผ],๐โ[๐ฝ],โ โ[๐ก+1]
1 ร h ร i
(โ )
= Pr ๐๐๐ | ๐ง = ๐ข
2๐
๐ขโ{0,1} ๐ ๐โ[๐ผ],๐โ[๐ฝ],โ โ[๐ก+1]
1 ร h ร i ๐ก+1
(1)
= Pr ๐๐๐ | ๐ง = ๐ข
2๐
๐ขโ{0,1} ๐ ๐โ[๐ผ],๐โ[๐ฝ]
1 ร h ร i ๐ก+1
(1)
โฅ Pr ๐๐๐ | ๐ง = ๐ข
2๐
๐ขโ{0,1} ๐ ๐โ[๐ผ],๐โ[๐ฝ]
ร ๐ก+1
(1)
= Pr ๐๐๐ ,
๐โ[๐ผ],๐โ[๐ฝ]
where the first equality holds by the law of total probability; the third equality holds because,
(โ )
conditioned on ๐ง taking a specific value, the events ๐โ[๐ผ],๐โ[๐ฝ] ๐๐๐ for โ โ [๐ก + 1] are independent
ร
and have the same probability; the inequality follows from the Hรถlderโs inequality.
We use a similar argument to obtain
h ร i hร i๐ผ
(1) (1)
Pr ๐๐๐ โฅ Pr ๐1๐ ,
๐โ[๐ผ],๐โ[๐ฝ] ๐โ[๐ฝ]
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 28
S UBLINEAR -T IME C OMPUTATION IN THE P RESENCE OF O NLINE E RASURES
(1) (1)
where we condition on the values of ๐ฆ1 , . . . , ๐ฆ ๐ฝ , and ๐ง. Similarly, by conditioning on the values
(1)
of ๐ฅ 1 and ๐ง, we obtain
hร i
โฅ (Pr[๐11 ])๐ฝ .
(1) (1)
Pr ๐1๐
๐โ[๐ฝ]
(1)
Since Pr[๐11 ] = ๐, the claim follows.
๐
ร the case when ๐ ๐ is small. For ๐ข1 , ๐ข2 , ๐ข3 โ {0, 1} , let span(๐ข1 , ๐ข2 , ๐ข3 ) be
Next, we consider
the set of points ๐โ๐ ๐ข ๐ for โ
โ ๐ โ [3] and
ร
(โ ) (โ )
๐= span(๐ฅ ๐ , ๐ฆ ๐ , ๐ง).
๐โ[๐ผ],๐โ[๐ฝ],โ โ[๐ก+1]
The set ๐ has (๐ผ + ๐ฝ)(๐ก + 1) + 1 singletons, at most ๐ผ(๐ฝ + 1)(๐ก + 1) double sums, and at most ๐ผ๐ฝ(๐ก + 1)
triple sums. Therefore, |๐| โค 3๐ผ๐ฝ(๐ก + 1).
๐๐
Claim 5.13. Suppose ๐ ๐ โค 2|๐|
1
. Then ๐0 โฅ 2 .
Proof. Let ๐ be a closest quadratic function to ๐ . Any two elements of ๐ are uniformly and
(โ ) (โ )
independently distributed in {0, 1} ๐ . Then, for ๐ฅ ๐ , ๐ฆ ๐ , ๐ง โผ {0, 1} ๐ , we have
๐0 โฅ Pr[ ๐ (๐ง) โ ๐(๐ง) and ๐ (๐ข) = ๐(๐ข) โ ๐ข โ ๐ \ {๐ง}]
ร
โฅ Pr[ ๐ (๐ง) โ ๐(๐ง)] โ [ ๐ (๐ง) โ ๐(๐ง) and ๐ (๐ข) โ ๐(๐ข)]
๐ขโ๐\{๐ง}
โฅ ๐ ๐ โ (|๐| โ 1)๐2๐ = ๐ ๐ (1 โ (|๐| โ 1)๐ ๐ ).
If ๐ ๐ โค 2|๐|
1
, then 1 โ (|๐| โ 1)๐ ๐ โฅ 1 โ |๐| ยท 2|๐|
1
โฅ 12 , which concludes the proof.
1
Suppose 2|๐| โค ๐ ๐ โค 7ยท40
3
. In this case, by Claim 5.10 and Claim 5.11 and using the fact that
|๐| โค 3๐ผ๐ฝ(๐ก + 1), we have
7 ๐ผ๐ฝ(๐ก+1) 7 ๐ผ๐ฝ(๐ก+1) 7
๐0 โฅ ๐๐ โฅ โฅ .
3 6 ยท |๐| (18 ยท ๐ผ๐ฝ(๐ก + 1))๐ผ๐ฝ(๐ก+1)
Finally, if ๐ ๐ โฅ 40
1
, then again by Claim 5.10 and Claim 5.11, we have ๐0 โฅ 40(๐ผ๐ฝ(๐ก+1))
1
. We have
๐
obtained that ๐ โฅ min 2 , (18ยท๐ผ๐ฝ(๐ก+1))๐ผ๐ฝ(๐ก+1) .
0
7
5.3 Proof of Lemma 5.4
In this section, we prove Lemma 5.4, which shows that conditioned on the good event ๐ โฉ ๐ข,
all queries in one round of Algorithm 3 are successfully obtained. In particular, this probability
only depends on the per-query erasure budget ๐ก.
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 29
I DEN K ALEMAJ , S OFYA R ASKHODNIKOVA , AND N ITHIN VARMA
Proof of Lemma 5.4. We first prove a lower bound on the probability that the queries made in
Step 9 are successfully obtained.
Claim 5.14. Conditioned on the event ๐ โฉ ๐ข, the probability that in one execution of Step 9 at level
๐ โ [0, ๐ก], all queries in the step are successfully obtained is at least
(๐ก+1)(2๐ก+1) ๐กโ๐
1
.
(๐ก 2 + ๐ก)(2๐ก + 1)๐กโ๐ + 1
Proof. Fix the values of โ , ๐, ๐1 , . . . , ๐๐ for the given execution of Step 9 and let ๐ = (โ , ๐1 , . . . , ๐๐ ).
We can assume, without loss of generality, that Step 6 considers the tuples (๐1 , . . . , ๐๐ ) in the
lexicographic order. When ๐๐ = 1, then right before Step 9 is executed, we have |๐ ๐ (โ1) | =
(๐ก + 1)(2๐ก + 1)๐กโ๐+1 . The size of the set ๐ ๐ (โ1) decreases as the value of ๐๐ increases, so that for
๐๐ = ๐ก + 1, we have
|๐ ๐ (โ1) | = (๐ก + 1)(2๐ก + 1)๐กโ๐+1 โ ๐ก(๐ก + 1)(2๐ก + 1)๐กโ๐
= (๐ก + 1)(2๐ก + 1)๐กโ๐ (2๐ก + 1 โ ๐ก) = (๐ก + 1)2 (2๐ก + 1)๐กโ๐ .
Thus, right before Step 9 is executed, the size of ๐ ๐ (โ1) is at least (๐ก + 1) times the size of the subset
๐๐ .
Let ๐ denote the size of ๐ ๐ (โ1) right before the execution of Step 8. In Step 8 we sample a
uniformly random subset ๐ ๐ of ๐ ๐ (โ1) of size ๐ 0 = (๐ก + 1)(2๐ก + 1)๐กโ๐ and in Step 9 we query ๐ฅ โ ๐ฆ ๐
for all ๐ฅ โ ๐ ๐ . Conditioned on the event ๐ โฉ ๐ข, all sums ๐ฅ โ ๐ฆ ๐ , where ๐ฅ โ ๐ ๐ , are distinct and
nonerased right before ๐ฆ ๐ is queried. On the ๐-th query of Step 9, the tester selects a uniformly
random ๐ฅ out of ๐ โ (๐ โ 1) elements. Right before the ๐-th query of the tester, the oracle can
have erased at most ๐ก๐ of the sums ๐ฅ โ ๐ฆ ๐ , for ๐ฅ โ ๐ ๐ (โ1) , since the adversary is not aware of the
points belonging to ๐ ๐ until their sums with ๐ฆ ๐ are queried in Step 9. Therefore, the probability
๐ก๐
that the tester successfully obtains the sum on its ๐-th query is at least 1 โ ๐ โ๐+1 , where ๐ โ [๐ 0].
We argued that, for all values of ๐๐ , right before the execution of Step 9, it always holds that
๐ โฅ (๐ก + 1)๐ 0. Therefore, the probability that the tester successfully obtains a sum is always
positive. In particular, using the bound ๐ โฅ (๐ก + 1)๐ 0, the probability that all queries in Step 9 are
successfully obtained is at least
๐ 0
๐ก๐ ๐ก๐ 0 ๐ ๐ 1 ๐
ร 0 0 0
1
1โ โฅ 1โ โฅ = .
๐ โ๐+1 ๐ โ ๐ 0 + 1 (๐ก + 1)๐ 0 โ ๐ 0 + 1 ๐ 0๐ก + 1
๐=1
Substituting ๐ 0 = (๐ก + 1)(2๐ก + 1)๐กโ๐ concludes the proof.
In Steps 4-11, the tester makes only singleton and double queries. Conditioned on ๐ โฉ ๐ข,
all singleton queries are successfully obtained. All double queries are made in Step 9. By
Claim 5.14, the probability that all double queries in Step 9 are successfully obtained depends
only on ๐ก.
Before ๐ง is queried in Step 11, conditioned on the event ๐ โฉ ๐ข, all double and triple sums
of the form ๐ฆ ๐ (๐) โ ๐ง, ๐ฅ โ ๐ง, and ๐ฅ โ ๐ฆ ๐ (๐) โ ๐ง, where ๐ โ [0, ๐ก], ๐ = (โ , ๐1 . . . , ๐๐ก ) โ [๐ก + 1](๐ก+1) ,
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 30
S UBLINEAR -T IME C OMPUTATION IN THE P RESENCE OF O NLINE E RASURES
and ๐ฅ โ ๐ ๐ , are distinct and nonerased. After ๐ง is queried, the oracle can perform at most ๐ก
erasures. Therefore, there exists โ โ [๐ก + 1], say โ = 1, such that all double and triple sums
๐ฆ ๐ (๐) โ ๐ง, ๐ฅ โ ๐ง, and ๐ฅ โ ๐ฆ ๐ (๐) โ ๐ง, where ๐ โ [0, ๐ก], ๐ = (1, ๐1 . . . , ๐๐ก ) โ [๐ก + 1](๐ก+1) , and ๐ฅ โ ๐ ๐ , are
nonerased after ๐ง is queried. With probability ๐ก+1 1
, the tester samples โ = 1 in Step 12. By a
similar reasoning, with probability (๐ก+1)๐ก the tester samples values of ๐1 , . . . , ๐๐ก in Step 12, say
1
๐1 = ยท ยท ยท = ๐๐ก = 1, such that all queries ๐ฆ ๐ (๐) โ ๐ง, where ๐ โ [0, ๐ก], are successfully obtained. In
addition, right before ๐ฆ ๐ (๐ก) โ ๐ง is queried, all sums of the form ๐ฅ โ ๐ง and ๐ฅ โ ๐ฆ ๐ (๐) โ ๐ง, where
๐ = (1, . . . , 1, ๐๐ก ) โ [๐ก + 1](๐ก+1) , ๐ โ [0, ๐ก], and ๐ฅ โ ๐ ๐ , are nonerased.
After ๐ฆ ๐ (๐ก) โ ๐ง is queried, the oracle performs at most ๐ก erasures, so there exists ๐ฅ โ ๐ ๐ such
that ๐ฅ โ ๐ง and ๐ฅ โ ๐ฆ ๐ (๐) โ ๐ง, where ๐ = (1, 1, . . . , 1) and ๐ โ [0, ๐ก], are nonerased. With probability
๐ก+1 , the tester samples this ๐ฅ in Step 13, and with probability ๐ก+1 , it samples ๐ โ [0, ๐ก] such that
1 1
the triple sum ๐ฅ โ ๐ฆ ๐ (๐) โ ๐ง is successfully obtained in Step 14. Thus, with probability (๐ก+1) 1
๐ก+3 , all
queries in Steps 12-14 are successfully obtained. Therefore the probability that all queries in one
round of Algorithm 3 are successfully obtained, conditioned on ๐ โฉ ๐ข, is 1/๐ ๐ก , where ๐ ๐ก is a
constant depending only on ๐ก.
6 Online-erasure-resilient sortedness testing
In this section, we prove Theorem 1.5 on the impossibility of general online-erasure-resilient
sortedness testing and Theorem 1.6 on online-erasure-resilient sortedness testing of sequences
with few distinct values.
6.1 Impossibility of online-erasure-resilient sortedness testing
In this section, we prove Theorem 1.5 which shows that online-erasure-resilient testing of
sortedness of integer sequences is impossible.
Proof of Theorem 1.5. By Yaoโs principle (see Corollary 9.4), it is enough to give a pair of distribu-
tions, one over monotone functions over [๐] and the other one over functions over [๐] that are
far from monotone, and an adversarial strategy, such that there is no deterministic algorithm
that can distinguish the distributions with high probability, when given access to them via a
1-online-erasure oracle that uses the given strategy.
Let ๐ โ โ be even. Consider the following distributions on functions ๐ : [๐] โ [๐].
๐ + distribution: Independently for all ๐ โ [๐/2]:
โข ๐ (2๐ โ 1) โ 2๐ โ 1 and ๐ (2๐) โ 2๐ โ 1, with probability 1/3.
โข ๐ (2๐ โ 1) โ 2๐ โ 1 and ๐ (2๐) โ 2๐, with probability 1/3.
โข ๐ (2๐ โ 1) โ 2๐ and ๐ (2๐) โ 2๐, with probability 1/3.
๐ โ distribution: Independently for all ๐ โ [๐/2]:
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 31
I DEN K ALEMAJ , S OFYA R ASKHODNIKOVA , AND N ITHIN VARMA
โข ๐ (2๐ โ 1) โ 2๐ and ๐ (2๐) โ 2๐ โ 1, with probability 1/3.
โข ๐ (2๐ โ 1) โ 2๐ โ 1 and ๐ (2๐) โ 2๐, with probability 2/3.
Every function sampled from the distribution ๐ + is monotone.
For a function sampled from the distribution ๐ โ , the expected number of index pairs
(2๐ โ 1, 2๐) such that the respective function values are 2๐ and 2๐ โ 1 is equal to ๐/6. By a
Chernoff bound, the probability that the number of such index-pairs is less than ๐/12 is at most
exp(โ๐/48). In other words, with probability at least 1 โ exp(โ๐/48), a function sampled from
the ๐ โ distribution is 1/12-far from being monotone.
Consider a deterministic adaptive algorithm ๐ with two-sided error for online-erasure-
1
resilient 12 -testing of monotonicity of functions from [๐] to [๐]. Assume that ๐ is given access
to a function sampled from ๐ + or ๐ โ with equal probability, where the access is via a 1-online-
erasures oracle. The oracle uses the following strategy. For each ๐ โ [๐/2], if ๐ queries the point
2๐ โ 1, then the oracle erases the function value at the point 2๐; if ๐ queries the point 2๐ then the
oracle erases the function value at the point 2๐ โ 1. The oracle erases exactly one function value
between queries. Given this strategy, the tester ๐ never sees a violation to monotonicity.
The distribution of function values restricted to any particular index is identical for distribu-
tions ๐ + and ๐ โ . Hence, the tester ๐ cannot distinguish the distributions, no matter how many
queries it makes.
6.2 Online-erasure-resilient testing of sortedness with small ๐
โ
๐
In this section, we prove Theorem 1.6 by showing that ๐( ๐ ) uniform queries are sufficient for
๐ก-online-erasure-resilient ๐-testing of sortedness, when ๐, the number of distinct values in the
sequence, is small. Pallavoor et al. [53] gave a 1-sided error ๐-tester
โ
for sortedness of real-valued
๐
sequences containing at most ๐ distinct values that makes ๐( ๐ ) uniform and independent
queries. The proof of [53, Theorem 1.5] is the starting point for our analysis.
Proof of Theorem 1.6. We call (๐ข, ๐ฃ) โ [๐]2 a violating pair if ๐ข < ๐ฃ and ๐ (๐ข) > ๐ (๐ฃ). The tester,
given
โ
input ๐ โ (0, 1) and oracle access to a function ๐ with image size at most ๐, queries ๐ on
2๐ ๐
๐ points selected uniformly and independently and rejects if and only if it queries ๐ข, ๐ฃ โ [๐]
such that (๐ข, ๐ฃ) is a violating pair. Since the decision made by the tester does not depend on the
specific values being queried, but only on the ordering of the queried values, we can assume
without loss of generality that the input function is of the form ๐ : [๐] โ [๐]. Clearly, the tester
accepts all sorted functions. We show that for ๐ = 32, if ๐ is ๐-far from sorted, the tester rejects
with probability at least 23 .
Suppose ๐ is ๐-far from sorted. Define the violation graph ๐บ([๐], ๐ธ) to be the graph whose
edges are the violating pairs (๐ข, ๐ฃ) โ [๐]2 . Dodis et al. [28, Lemma 7] show that ๐บ has a matching
๐ of size at least ๐๐/2. For each range value ๐ โ [๐], let ๐ ๐ be the set of edges (๐ข, ๐ฃ) โ ๐ whose
lower endpoint ๐ข has value ๐, i.e., ๐ (๐ข) = ๐. Let ๐ฟ ๐ consist of the |๐ ๐ |/2 smallest indices amongst
the lower endpoints of the edges in ๐ ๐ . Let ๐ ๐ consist of the |๐ ๐ |/2 largest indices amongst
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 32
S UBLINEAR -T IME C OMPUTATION IN THE P RESENCE OF O NLINE E RASURES
the upper endpoints of the edges in ๐ ๐ . It is not hard to see that, for every ๐ โ [๐], all pairs in
๐ฟ ๐ ร ๐ ๐ are violating. By construction,
ร ร ร |๐| ๐๐
|๐ฟ ๐ | = |๐ ๐ | = |๐ ๐ |/2 = โฅ . (6.1)
2 4
๐โ[๐] ๐โ[๐] ๐โ[๐]
We show that with probability at least 23 , for some ๐ โ [๐], the tester samples a nonerased element
both from ๐ฟ ๐ and from ๐ ๐ , in which case it rejects.
Our proof relies on the following claim from [36], for which we first introduce some notation.
Let ๐ฟ1 , . . . , ๐ฟ๐ be disjoint subsets of [๐]. Let ๐ ๐ = |๐ฟ๐๐ | and ๐ = ๐โ[๐] ๐ ๐ . Suppose we sample
ร
โ
๐ ๐/๐ uniform points from [๐]. Let ๐ผ be a random variable denoting the set of indices ๐ โ [๐]
such that the sample contains at least one element from the set ๐ฟ ๐ .
Claim 6.1 (Claim 1 of [36]). With probability 1 โ eโ๐ over the choice of the sample,
ร ๐
๐๐ โฅ โ .
๐โ๐ผ
๐
โ
๐ ๐
๐ each. Let ๐ฟ ๐ โ ๐ฟ ๐ be the set of nonerased indices
0
Split the sample into two parts of size
|๐ฟ0 |
of ๐ฟ ๐ after the tester queries the first part of the sample, and define ๐ ๐0 similarly. Let ๐ 0๐ = ๐๐ ,
|๐ 0 |
๐ 0๐ = ๐๐ , and ๐0 = ๐โ[๐] min(๐ 0๐ , ๐ 0๐ ). Without loss of generality assume ๐ 0๐ โค ๐ 0๐ for all ๐ โ [๐]. The
ร
โ
๐ ๐๐ก
adversary performs at most ๐ erasures after the first part of the sample is queried, therefore
ร |๐ฟ0 | ร |๐ฟ | ๐ โ๐๐ก ๐ ๐ ๐๐ก
โ
๐
0 ๐ ๐
๐ = โฅ โ โฅ โ โฅ ,
๐ ๐ ๐๐ 4 ๐๐ 8
๐โ[๐] ๐โ[๐]
โ ๐2 ๐
where we use (6.1) and the assumption that ๐ โค ๐ โค 8๐ 2 ๐ก . Let ๐ผ be a random variable denoting
0
the set of indices ๐ โ [๐] such that at least one element of ๐ฟ0๐ is contained in the first part of the
๐
sample. By Claim 6.1, with probability 1 โ eโ 8 over the first part of the sample,
ร ๐
๐ 0๐ โฅ โ . (6.2)
๐โ๐ผ 0 8 ๐
The probability that the second part of the sample does not include a nonerased element from
โช๐โ[๐]๐ ๐0 is
โ ๐ โ๐ โ
๐๐๐
ร ๐ ๐๐ก ๐
๐ ๐ ๐
1โ ๐ 0๐ + โค 1โ โ + โ โค eโ 16 ,
๐๐ 8 ๐ 16 ๐
๐โ[๐]
where we use (6.2) to lower bound ๐โ[๐] ๐ 0๐ , and the assumption that ๐ < ๐๐๐ก๐ to upper bound
ร 2
the number of erasures. Therefore, the probability that for some ๐ โ [๐] the tester samples a
nonerased element both from ๐ฟ ๐ and ๐ ๐ and rejects is at least
๐ ๐ 2
(1 โ eโ 8 ) ยท (1 โ eโ 16 ) โฅ ,
3
where the inequality holds for ๐ = 32.
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 33
I DEN K ALEMAJ , S OFYA R ASKHODNIKOVA , AND N ITHIN VARMA
7 Impossibility of online-erasure-resilient Lipschitz testing
In this section, we prove Theorem 1.7. We start by showing that 1-online-erasure-resilient
Lipschitz testing of functions ๐ : [๐] โ {0, 1, 2} is impossible.
Proof of Theorem 1.7, part 1. We prove the theorem using Yaoโs principle. The proof is analogous
to that of Theorem 1.5 once the hard distributions are described. In particular, the strategy of
the oracle is identical to that used in the proof of Theorem 1.5.
Let ๐ โ โ be a multiple of 4. The following distributions are over functions ๐ : [๐] โ {0, 1, 2}.
Distribution ๐ + : Independently, for all ๐ โ [๐] such that ๐ mod 4 โก 1:
โข ๐ (๐) โ 0 and ๐ (๐ + 1) โ 1, with probability 1/2.
โข ๐ (๐) โ 1 and ๐ (๐ + 1) โ 2, with probability 1/2.
Independently, for all ๐ โ [๐] such that ๐ mod 4 โก 3:
โข ๐ (๐) โ 1 and ๐ (๐ + 1) โ 0, with probability 1/2.
โข ๐ (๐) โ 2 and ๐ (๐ + 1) โ 1, with probability 1/2.
Distribution ๐ โ : Independently, for all ๐ such that ๐ mod 4 โก 1:
โข ๐ (๐) โ 0 and ๐ (๐ + 1) โ 2, with probability 1/2.
โข ๐ (๐) โ 1 and ๐ (๐ + 1) โ 1, with probability 1/2.
Independently, for all ๐ such that ๐ mod 4 โก 3:
โข ๐ (๐) โ 2 and ๐ (๐ + 1) โ 0, with probability 1/2.
โข ๐ (๐) โ 1 and ๐ (๐ + 1) โ 1, with probability 1/2.
Every function sampled from the distribution ๐ + is Lipschitz. For a function sampled from
the distribution ๐ โ , the expected distance to being Lipschitz is 1/4. The rest of the proof is
similar to that of Theorem 1.5.
Next, we prove the second part of Theorem 1.7 showing that 1-online-erasure-resilient
Lipschitz testing of functions ๐ : {0, 1} ๐ โ {0, 1, 2} is impossible.
Proof of Theorem 1.7, part 2. The proof is analogous to the proof of the first part of the theorem
once the hard distributions are described.
The following distributions are over functions ๐ : {0, 1} ๐ โ {0, 1, 2}. Let ๐1 โ {0, 1} ๐ denote
the first standard basis vector.
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 34
S UBLINEAR -T IME C OMPUTATION IN THE P RESENCE OF O NLINE E RASURES
Distribution ๐ + : Independently, for all ๐ฅ โ {0, 1} ๐ such that ๐ฅ 1 = 0:
โข ๐ (๐ฅ) โ 0 and ๐ (๐ฅ โ ๐1 ) โ 1, with probability 1/2.
โข ๐ (๐ฅ) โ 1 and ๐ (๐ฅ โ ๐1 ) โ 2, with probability 1/2.
Distribution ๐ โ : Independently, for all ๐ฅ โ {0, 1} ๐ such that ๐ฅ 1 = 0:
โข ๐ (๐ฅ) โ 0 and ๐ (๐ฅ โ ๐1 ) โ 2, with probability 1/2.
โข ๐ (๐ฅ) โ 1 and ๐ (๐ฅ โ ๐1 ) โ 1, with probability 1/2.
Every function sampled from the distribution ๐ + is Lipschitz. For a function sampled from the
distribution ๐ โ , the expected distance to being Lipschitz is 1/4. The rest of the proof is similar
to that of Theorem 1.5. This completes the proof of Theorem 1.7.
8 Computation in the presence of online corruptions
This section discusses implications of our results to computation in the presence of online
corruptions.
8.1 Online-corruption-resilience from online-erasure-resilience in testing
In this section, we prove Lemma 1.8, showing that an algorithm that accesses its input via an
online-erasure oracle and, with high probability, encounters no erasures and outputs a correct
answer, is also correct with high probability for all adversarial strategies (and for the same
computational task) when it accesses its input via an online-corruption oracle.
Proof of Lemma 1.8. Fix an input function ๐ and a strategy of the ๐ก-online-corruption oracle for
this function. Let ๐ช (๐) denote an oracle that uses this strategy. Map the strategy of ๐ช (๐) to a
strategy for a ๐ก-online-erasure oracle ๐ช (๐) , so that whenever ๐ช (๐) modifies the value at a point
๐ฅ to ๐ช (๐) (๐ฅ) โ ๐ (๐ฅ), the online-erasure oracle erases the value at the same point, i.e., it sets
๐ช (๐) (๐ฅ) =โฅ.
Fix the random coins of an execution of ๐, where access to ๐ is via ๐ช (๐) , and for which all
queries are successfully obtained and ๐ outputs a correct answer. Let ๐ (๐) be the execution of ๐
with those coins. Similarly, let ๐ (๐) be the execution of ๐ with the same coins, when access to ๐
is via ๐ช (๐) . Since ๐ (๐) encounters no erasures, ๐ (๐) will make the same queries as ๐ (๐) and get
the same query answers. Consequently, ๐ (๐) will also output the same (correct) answer as ๐ (๐) .
Therefore, when ๐ accesses ๐ via an online-corruption oracle, it outputs a correct answer with
probability at least 2/3.
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 35
I DEN K ALEMAJ , S OFYA R ASKHODNIKOVA , AND N ITHIN VARMA
8.2 Online-corruption-resilient linearity tester
In this section, we show the existence of a 2-sided error, online-corruption-resilient tester for
linearity.
Corollary 8.1. There exists ๐ 0 โ (0, 1) and a nonadaptive, ๐ก-online-corruption-resilient ๐-tester for
linearity of functions ๐ : {0, 1} ๐ โ {0, 1} that works for ๐ก โค ๐0 ยท ๐5/4 ยท 2๐/4 and makes ๐( 1๐ log ๐๐ก )
queries.
Proof. Consider Algorithm 1, modified to use ๐ = 2 log ๐ถ๐ก ๐2
for ๐ถ = 3000. Note that the larger the
size ๐ of the reserve, the higher is the probability that Algorithm 1 detects a violation to linearity.
For the choice of ๐ = 2 log 3000๐ก
๐2
, Algorithm 1 is also a 1-sided error online-erasure-resilient tester.
Furthermore, for this choice of ๐, Algorithm 1 rejects with probability at least 5/6 (as opposed
to 2/3) when ๐ is ๐-far from linear.
By Lemma 1.8, it remains to show that, for all adversarial strategies, Algorithm 1 queries an
erased point during its execution with probability at most 1/6. Fix an adversarial strategy and
one round of Algorithm 1. (Recall that each iteration of the outer repeat loop in Steps 3-9 is
๐
called a round). Let ๐บ be the event defined in Lemma 2.8 for the fixed round. Then Pr[๐บ] โค 800 .
Let ๐ต denote the event that the algorithm queries an erased point during the fixed round.
Then
Pr[๐ต] = Pr[๐ต | ๐บ] Pr[๐บ] + Pr[๐ต | ๐บ] Pr[๐บ] โค Pr[๐ต | ๐บ] + Pr[๐บ].
To upper bound Pr[๐ต | ๐บ] it suffices to upper bound the probability that the algorithm queries
an erased sum in some iteration of Step 8 of the fixed round. Since ๐บ occurred, there are at least
2๐โ1 โ 1 distinct sums that can be queried in Step 8, all of them nonerased at the beginning of the
round. Algorithm 1 makes at most ๐ + 4 ยท 2 ๐ โค ๐ + 32 ๐ queries in this round. Thus, the fraction of
these sums erased during the round is at most
๐ + 32
๐
1 70 ๐2 70๐3
2 1 8.75 ๐2
๐กยท โค๐กยท + โค + โค ๐ + โค ,
2๐โ1 โ 1 2๐/2 ๐ ยท 2๐ ๐ถ 4๐ก ยท ๐ถ 2 ๐ถ ๐ถ2 88 ยท 32
๐
where in the first inequality we used that 2๐โ1 โ1 โค 2๐/2
1
for ๐ โฅ 9 and that (2๐โ1 โ 1)/32 โฅ 2๐ /70 for
๐ โฅ 5 (note that ๐ โฅ 2 log(3000๐ก/๐ ) โฅ 25), in the second inequality we used ๐ โฅ 2 log(3000๐ก/๐2 ),
2
and in the third inequality we used ๐ โค 12 .
Since there are at most 4 ยท 2 ๐ โค 32
๐ iterations of Step 8, we obtain by a union bound that
32 ๐2 ๐
Pr[๐ต | ๐บ] โค
ยท = .
๐ 88 ยท 32 88
๐ ๐ ๐
Consequently, Pr[๐ต] โค 88 + 800 โค 80 . The number of rounds of Algorithm 1 is at most
log 8/๐ log 8๐
ร 8 ln 5 8 ln 5 ร 1 8 ln 5
= โค .
2๐๐ ๐ 2 ๐ ๐
๐=1 ๐=1
Therefore, Algorithm 1 queries an erased point during its execution with probability at most
๐ ยท Pr[๐ต] โค 6 . This concludes the proof.
8 ln 5 1
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 36
S UBLINEAR -T IME C OMPUTATION IN THE P RESENCE OF O NLINE E RASURES
8.3 Online-corruption-resilient tester of sortedness with few distinct values
In this section, we show the existence of nonadaptive online-corruption-resilient tester for
sortedness of sequences with few distinct values.
Corollary 8.2. There exists a nonadaptive, ๐ก-online-corruption-resilient
โ
๐-tester for sortedness of ๐-
๐
element sequences with at most ๐ distinct values. The tester makes ๐( ๐ ) uniform and independent
queries and works when ๐ < ๐๐0๐๐ก , where ๐ 0 > 0 is a specific constant.
2
โ
2๐ ๐
Proof. Recall that the online-erasure-resilient sortedness tester makes ๐ uniform and indepen-
dent queries to ๐ : [๐] โ [๐]. The tester always accepts when ๐ is sorted. We can easily modify
the tester, without affecting its asymptotic query complexity, to reject with probability at least
5/6 (as opposed to 2/3) when ๐ is ๐-far from sorted. Then, by Lemma 1.8, it suffices to show
that, for all adversarial strategies, this โtester queries an erased point with probability at most
2๐ ๐๐ก
1/6. The adversary performs at most ๐ erasures during the execution of the algorithm. Since
the tester performs
โ
its queries uniformly at random, the probability that a given query is erased
2๐ ๐๐ก
is at most ๐๐ . By a union bound, the probability that some query of the tester is erased is at
๐2 ๐
most 4๐๐2 ๐๐๐ก . Set ๐ 0 = 24๐ 2 . By our assumption that ๐ < 24๐
2
2 ๐ก , we obtain that the probability that
the tester samples an erased point is at most 6 . 1
8.4 Finding witnesses in the presence of online corruptions
In this section, we prove Lemma 1.9. Specifically, we show how to modify a nonadaptive, 1-sided
error, online-erasure-resilient tester for a property ๐ซ to get an algorithm that accesses the input
via an online-corruption oracle and outputs a witness demonstrating the violation of ๐ซ.
Proof of Lemma 1.9. Let ๐ be a nonadaptive, 1-sided error, ๐ก-online-erasure-resilient tester for
๐ซ. Let ๐ be ๐-far from ๐ซ. Fix a strategy of the ๐ก-online-corruption oracle, and let ๐ช (๐) denote
the oracle running this strategy. Define a a ๐ก-online-erasure oracle ๐ช (๐) that follows the same
strategy as ๐ช (๐) , except that ๐ช (๐) erases the value at each point ๐ฅ that ๐ช (๐) modifies, i.e., it sets
๐ช (๐) (๐ฅ) =โฅ.
If the tester ๐ accesses ๐ via ๐ช (๐) , it rejects with probability at least 2/3. Fix the random coins
of an execution of ๐ for which it rejects. Let ๐ (๐) be the execution of ๐ with those coins (where
access to ๐ is via ๐ช (๐) ). Similarly, let ๐ (๐) be the execution of ๐ with the same coins when access
to ๐ is via ๐ช (๐) . Since ๐ is nonadaptive, ๐ (๐) and ๐ (๐) make the same queries. By definition of ๐ช (๐) ,
if ๐ (๐) obtains ๐ (๐) (๐ฅ) = ๐ (๐ฅ) for a query ๐ฅ, then ๐ (๐) obtains ๐ (๐) (๐ฅ) = ๐ (๐ฅ) for the same query.
Since ๐ (๐) is a 1-sided error tester, it can reject only if it successfully obtains values of ๐ on
some queried points ๐ฅ 1 , . . . , ๐ฅ ๐ such that no ๐ โ ๐ซ has ๐(๐ฅ ๐ ) = ๐ (๐ฅ ๐ ) for all ๐ โ [๐]. Then, for the
same queries, ๐ (๐) obtains ๐ช (๐) (๐ฅ 1 ) = ๐ (๐ฅ 1 ), . . . , ๐ช (๐) (๐ฅ ๐ ) = ๐ (๐ฅ ๐ ). Therefore, ๐ (๐) finds a witness
of ๐ โ ๐ซ. We modify ๐ to output a witness if it finds one. (Note that ๐ (๐) and ๐ (๐) might output
different sets of points violating ๐ซ, since ๐ (๐) will obtain additional values ๐ช (๐) (๐ฅ) โ โ for the
queries ๐ฅ for which ๐ (๐) obtained ๐ช (๐) (๐ฅ) =โฅ.) Now, if we run the modified ๐ with access to ๐
via ๐ช (๐) , it outputs a witness of ๐ โ ๐ซ with probability at least 2/3.
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 37
I DEN K ALEMAJ , S OFYA R ASKHODNIKOVA , AND N ITHIN VARMA
9 Yaoโs minimax principle for online erasure oracles
We extend Yaoโs minimax principle [72] to the setting of online erasures, so that it can be used
to prove lower bounds on the query complexity of randomized online-erasure-resilient testers.
In the standard property testing model, Yaoโs principle allows one to prove a lower bound on
query complexity by describing a distribution on inputs that is hard to test, in the sense that a
deterministic algorithm needs many queries to decide, with high probability over the input,
whether an input sampled from the distribution has the property or is far from it. In the setting
of online erasures, we show that one can prove a lower bound by describing a distribution on
inputs as well as an oracle erasure strategy such that every deterministic algorithm that accesses
the input selected from the distribution via the erasure oracle needs many queries to test a
specified property with high probability.
Theorem 9.1. To prove a lower bound ๐ on the worst-case query complexity of online-erasure-resilient
randomized algorithms that perform a specified computational task with error probability strictly less
than 13 , it is enough to give a distribution ๐ on inputs of size ๐ and a (randomized) oracle erasure strategy
๐ฎ, such that every deterministic algorithm making at most ๐ queries to an input drawn from ๐ via an
online-erasure oracle that uses strategy ๐ฎ, errs with probability at least 13 .
Proof. We prove a min-max inequality similar to Yaoโs original min-max inequality [72]. The
inequality relates the error complexities of the algorithms, rather than their query complexity,
which we will fix beforehand. Consider a randomized algorithm for the specified task that,
given access to an input object of size ๐ via a ๐ก-online-erasure oracle, makes at most ๐ queries,
and may be incorrect with some probability. We can represent the randomized algorithm as a
probability distribution ๐ on the set of all (possibly incorrect) deterministic algorithms ๐ด with
query complexity at most ๐. Let ๐ ๐ denote the set of such algorithms, and let ๐(๐ด) denote the
probability of drawing algorithm ๐ด from the set ๐ ๐ .
Denote by ๐๐ the set of inputs of size ๐ for the computational task. Let ๐ฎ๐,๐ be the set
of deterministic erasure strategies of the ๐ก-online-erasure oracle for inputs of size ๐ against
algorithms of query complexity at most ๐. An adversarial strategy can be represented by a
decision tree that, based on the input and the queries of the algorithm, indicates which input
entries to erase next. Since we are only considering inputs of fixed size and algorithms of
bounded query complexity, the set of oracle strategies has finite cardinality. Oracle strategies can
be randomized, so we consider a distribution on deterministic strategies. For ease of notation,
we consider a joint distribution on inputs and oracle strategies, i.e., we let ๐ be a distribution
on the input-strategy pairs ๐๐ ร ๐ฎ๐,๐ . Given an input ๐ฅ โ ๐๐ , an adversarial strategy ๐ โ ๐ฎ๐,๐ ,
and an algorithm ๐ด โ ๐ ๐ , let ๐ผ(๐ด, ๐ฅ, ๐ ) be the indicator function for ๐ด being incorrect on ๐ฅ,
i.e., ๐ผ(๐ด, ๐ฅ, ๐ ) = 1 if ๐ด is incorrect on ๐ฅ against an oracle that uses strategy ๐ , and ๐ผ(๐ด, ๐ฅ, ๐ ) = 0
otherwise.
We prove the following min-max inequality
ร ร
min max ๐ผ(๐ด, ๐ฅ, ๐ )๐(๐ด) โฅ max min ๐ผ(๐ด, ๐ฅ, ๐ )๐(๐ฅ, ๐ ). (9.1)
๐ (๐ฅ,๐ )โ๐๐ ร๐ฎ๐,๐ ๐ ๐ดโ๐ ๐
๐ดโ๐ ๐ (๐ฅ,๐ )โ๐๐ ร๐ฎ๐,๐
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 38
S UBLINEAR -T IME C OMPUTATION IN THE P RESENCE OF O NLINE E RASURES
We comment on how (9.1) implies Theorem 9.1. Suppose there exists some distribution ๐
on input-strategy pairs, such that every ๐-query deterministic algorithm errs with probability
at least 1/3 on an input-strategy pair drawn from ๐. This implies that the right-hand side
of (9.1) is at least 13 . (Note that we can express ๐ as a distribution ๐ on the inputs and a
randomized adversarial strategy ๐ฎ). By (9.1), every ๐-query randomized algorithm errs with
probability at least 13 for every input and adversarial strategy. Therefore, an algorithm for the
given computational task that errs with probability strictly less than 13 has to make at least ๐
queries, which implies Theorem 9.1.
We now prove (9.1). Fix distribution ๐ on algorithms and distribution ๐ on input-strategy
pairs. Then
ร ร ร
max ๐ผ(๐ด, ๐ฅ, ๐ )๐(๐ด) = ๐(๐ฅ, ๐ ) max ๐ผ(๐ด, ๐ฅ, ๐ )๐(๐ด)
(๐ฅ,๐ )โ๐๐ ร๐ฎ๐,๐ (๐ฅ,๐ )โ๐๐ ร๐ฎ๐,๐
๐ดโ๐ ๐ (๐ฅ,๐ )โ๐๐ ร๐ฎ๐,๐ ๐ดโ๐ ๐
ร ร
โฅ ๐(๐ฅ, ๐ ) ๐ผ(๐ด, ๐ฅ, ๐ )๐(๐ด)
(๐ฅ,๐ )โ๐๐ ร๐ฎ๐,๐ ๐ดโ๐ ๐
ร ร
= ๐(๐ด) ๐ผ(๐ด, ๐ฅ, ๐ )๐(๐ฅ, ๐ ) (9.2)
๐ดโ๐ ๐ (๐ฅ,๐ )โ๐๐ ร๐ฎ๐,๐
ร ร
โฅ ๐(๐ด) min ๐ผ(๐ด, ๐ฅ, ๐ )๐(๐ฅ, ๐ )
๐ดโ๐ ๐
๐ดโ๐ ๐ (๐ฅ,๐ )โ๐๐ ร๐ฎ๐,๐
ร
= min ๐ผ(๐ด, ๐ฅ, ๐ )๐(๐ฅ, ๐ ).
๐ดโ๐ ๐
(๐ฅ,๐ )โ๐๐ ร๐ฎ๐,๐
Crucially, the fact that ๐ ๐ , ๐๐ , and ๐ฎ๐,๐ have finite cardinalities allows us to exchange the order
of the sums in (9.2).
9.1 A version of Yaoโs minimax with two distributions
In this section, we prove a corollary to Theorem 9.1 which refers to the more common usage of
Yaoโs minimax principle for proving lower bounds, where separate distributions on positive
and negative instances are defined. The corollary is a generalization of Claim 5 in [60].
Definition 9.2. The statistical distance between two discrete distributions ๐1 and ๐2 is
๐ถ๐ท(๐1 , ๐2 ) = max Pr [๐ฅ โ ๐] โ Pr [๐ฅ โ ๐] .
๐โsupport(๐1 )โชsupport(๐2 ) ๐ฅโผ๐1 ๐ฅโผ๐2
Definition 9.3. Given a ๐-query deterministic algorithm ๐, let ๐(๐ฅ) be the string of ๐ answers
that ๐ receives when making queries to input object ๐ฅ. For a distribution ๐ and adversarial
strategy ๐ฎ, let ๐-view be the distribution on strings ๐(๐ฅ) where the input object ๐ฅ is sampled
from ๐ and accessed via a ๐ก-online-erasure oracle using strategy ๐ฎ.
Corollary 9.4. To prove a lower bound ๐ on the worst-case query complexity of online-erasure-resilient
randomized algorithms for a promise decision problem, it is enough to give
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 39
I DEN K ALEMAJ , S OFYA R ASKHODNIKOVA , AND N ITHIN VARMA
โข a randomized adversarial strategy ๐ฎ,
โข a distribution ๐ + on positive instances of size ๐, and
โข a distribution ๐ โ on instances of size ๐ that are negative with probability at least 67 ,
such that ๐ถ๐ท(๐ + -view, ๐ โ -view) < 16 for every deterministic ๐-query algorithm that accesses its input
via an online-erasure oracle using strategy ๐ฎ.
Our proof of Corollary 9.4 is similar to an argument in [60]. We rely on the following claim
from [60].
Claim 9.5 (Claim 4 of [60]). Let ๐ธ be an event that happens with probability at least 1 โ ๐ฟ under
the distribution ๐ and let โฌ be the distribution ๐ conditioned on ๐ธ. Then ๐ถ๐ท(๐, โฌ) โค ๐ฟ0, where
๐ฟ0 = 1โ๐ฟ
1
โ 1.
Proof of Corollary 9.4. Let ๐ด be a deterministic ๐-query algorithm for the promise decision
problem. Given distributions ๐ + and ๐ โ , we define a distribution ๐ satisfying the conditions
of Theorem 9.1. Let ๐ธ be the event that ๐ฅ โผ ๐ โ is a negative instance, and let โฌ be the distribution
๐ โ conditioned on the event ๐ธ. To obtain a sample from ๐, with probability 1/2 draw a sample
from ๐ + , and with probability 1/2 draw a sample from โฌ. We show that ๐ด errs with probability
at least 1/3 when it accesses an input object ๐ฅ โผ ๐ via the online-erasure oracle that uses
strategy ๐ฎ. Let ๐ be the set of query-answers strings ๐ on which ๐ด accepts. By the law of total
probability,
1 1
Pr [๐ด(๐ฅ) is correct] = Pr [๐ด(๐ฅ) accepts] + Pr [๐ด(๐ฅ) rejects]
๐ฅโผ๐ 2 ๐ฅโผ๐ + 2 ๐ฅโผโฌ
1 1
= + Pr [๐ด(๐ฅ) accepts] โ Pr [๐ด(๐ฅ) accepts]
2 2 ๐ฅโผ๐ + ๐ฅโผโฌ
1 1
= + Pr [๐ โ ๐] โ Pr [๐ โ ๐]
2 2 ๐โผ๐ + -view ๐โผโฌ-view
1 1
โค + ๐ถ๐ท(๐ + -view, โฌ-view).
2 2
Note that โฌ-view is the same as the distribution ๐ โ -view conditioned on the event ๐ธ. By
Claim 9.5 and the assumption that Pr๐ฅโผ๐ โ [๐ธ] โฅ 76 , we have ๐ถ๐ท(โฌ-view, ๐ โ -view) โค 16 . By the
triangle inequality,
1 1 1
๐ถ๐ท(๐ + -view, โฌ-view) โค ๐ถ๐ท(๐ + -view, ๐ โ -view) + ๐ถ๐ท(โฌ-view, ๐ โ -view, ) < + = .
6 6 3
Therefore, Pr๐ฅโผ๐ [๐ด(๐ฅ) is correct] < 12 + 21 ยท 13 = 23 .
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 40
S UBLINEAR -T IME C OMPUTATION IN THE P RESENCE OF O NLINE E RASURES
References
[1] Nir Ailon, Bernard Chazelle, Seshadhri Comandur, and Ding Liu: Estimating the distance
to a monotone function. Random Struct. Algor., 31(3):371โ383, 2007. [doi:10.1002/rsa.20167]
4
[2] Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, and Dana Ron:
Testing Reed-Muller codes. IEEE Trans. Inform. Theory, 51(11):4032โ4039, 2005.
[doi:10.1109/TIT.2005.856958] 3, 6, 7, 11, 24, 27
[3] Sanjeev Arora and Madhu Sudan: Improved low-degree testing and its applications.
Combinatorica, 23(3):365โ426, 2003. [doi:10.1007/s00493-003-0025-0] 6
[4] Pranjal Awasthi, Madhav Jha, Marco Molinaro, and Sofya Raskhodnikova: Test-
ing Lipschitz functions on hypergrid domains. Algorithmica, 74(3):1055โ1081, 2016.
[doi:10.1007/s00453-015-9984-y] 7
[5] Lรกszlรณ Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy: Checking com-
putations in polylogarithmic time. In Proc. 23rd STOC, pp. 21โ31. ACM Press, 1991.
[doi:10.1145/103418.103428] 6
[6] Lรกszlรณ Babai, Lance Fortnow, and Carsten Lund: Non-deterministic exponen-
tial time has two-prover interactive protocols. Comput. Complexity, 1(1):3โ40, 1991.
[doi:10.1007/BF01200056] 6
[7] Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak,
and Uri Stemmer: Dynamic algorithms against an adaptive adversary: generic con-
structions and lower bounds. In Proc. 54th STOC, pp. 1671โ1684. ACM Press, 2022.
[doi:10.1145/3519935.3520064] 4
[8] Mihir Bellare, Don Coppersmith, Johan Hรฅstad, Marcos A. Kiwi, and Madhu Sudan:
Linearity testing in characteristic two. IEEE Trans. Inform. Theory, 42(6):1781โ1795, 1996.
[doi:10.1109/18.556674] 3, 5, 12, 19, 20
[9] Mihir Bellare, Oded Goldreich, and Madhu Sudan: Free bits, PCPs, and
nonapproximabilityโtowards tight results. SIAM J. Comput., 27(3):804โ915, 1998.
[doi:10.1137/S0097539796302531] 5
[10] Mihir Bellare, Shafi Goldwasser, Carsten Lund, and Alexander Russell: Efficient
probabilistically checkable proofs and applications to approximations. In Proc. 25th STOC,
pp. 294โ304. ACM Press, 1993. [doi:10.1145/167088.167174] 5
[11] Mihir Bellare and Madhu Sudan: Improved non-approximability results. In Proc. 26th
STOC, pp. 184โ193. ACM Press, 1994. [doi:10.1145/195058.195129] 5
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 41
I DEN K ALEMAJ , S OFYA R ASKHODNIKOVA , AND N ITHIN VARMA
[12] Aleksandrs Belovs: Adaptive lower bound for testing monotonicity on the line. In
Proc. 22nd Internat. Conf. on Randomization and Computation (RANDOMโ18), pp. 31:1โ10.
Schloss DagstuhlโLeibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.APPROX-
RANDOM.2018.31] 4, 6, 7
[13] Omri Ben-Eliezer, Eldar Fischer, Amit Levi, and Ron D. Rothblum: Hard properties
with (very) short PCPPs and their applications. In Proc. 11th Innovations in Theoret. Comp.
Sci. Conf. (ITCSโ20), pp. 9:1โ27. Schloss DagstuhlโLeibniz-Zentrum fuer Informatik, 2020.
[doi:10.4230/LIPIcs.ITCS.2020.9] 4
[14] Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff, and Eylon Yogev: A frame-
work for adversarially robust streaming algorithms. J. ACM, 69(2):17:1โ33, 2022.
[doi:10.1145/3498334] 4
[15] Omri Ben-Eliezer and Eylon Yogev: The adversarial robustness of sampling. In Proc.
39th Symp. on Principles of Database Systems (PODSโ20), pp. 49โ62. ACM Press, 2020.
[doi:10.1145/3375395.3387643] 4
[16] Eli Ben-Sasson, Madhu Sudan, Salil P. Vadhan, and Avi Wigderson: Randomness-efficient
low degree tests and short PCPs via epsilon-biased sets. In Proc. 35th STOC, pp. 612โ621.
ACM Press, 2003. [doi:10.1145/780542.780631] 5
[17] Piotr Berman, Sofya Raskhodnikova, and Grigory Yaroslavtsev: ๐ฟ ๐ -testing. In Proc. 46th
STOC, pp. 164โ173. ACM Press, 2014. [doi:10.1145/2591796.2591887] 6, 7, 14, 15
[18] Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, and
David P. Woodruff: Transitive-closure spanners. SIAM J. Comput., 41(6):1380โ1425, 2012.
[doi:10.1137/110826655] 4
[19] Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, and David
Zuckerman: Optimal testing of Reed-Muller codes. In Proc. 51st FOCS, pp. 488โ497. IEEE
Comp. Soc., 2010. A version of this paper, by the same title and authors, appeared as a
chapter in โProperty Testing: Current Research and Surveysโ (Oded Goldreich, ed.), 2010,
pp. 269โ275, Springer LNCS vol. 6390. [doi:10.1109/FOCS.2010.54] 6, 11
[20] Eric Blais, Sofya Raskhodnikova, and Grigory Yaroslavtsev: Lower bounds for testing
properties of functions over hypergrid domains. In Proc. 29th IEEE Conf. on Comput.
Complexity (CCCโ14), pp. 309โ320. IEEE Comp. Soc., 2014. [doi:10.1109/CCC.2014.38] 7
[21] Manuel Blum, Michael Luby, and Ronitt Rubinfeld: Self-testing/correcting with applica-
tions to numerical problems. J. Comput. System Sci., 47(3):549โ595, 1993. [doi:10.1016/0022-
0000(93)90044-W] 3, 5
[22] Deeparnab Chakrabarty, Kashyap Dixit, Madhav Jha, and C. Seshadhri: Property testing
on product distributions: Optimal testers for bounded derivative properties. ACM Trans.
Algorithms, 13(2):20:1โ30, 2017. [doi:10.1145/3039241] 7
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 42
S UBLINEAR -T IME C OMPUTATION IN THE P RESENCE OF O NLINE E RASURES
[23] Deeparnab Chakrabarty and C. Seshadhri: Optimal bounds for monotonicity and Lipschitz
testing over hypercubes and hypergrids. In Proc. 45th STOC, pp. 419โ428. ACM Press, 2013.
[doi:10.1145/2488608.2488661] 4, 7
[24] Deeparnab Chakrabarty and C. Seshadhri: An optimal lower bound for mono-
tonicity testing over hypergrids. Theory of Computing, 10(17):453โ464, 2014.
[doi:10.4086/toc.2014.v010a017] 6
[25] Irit Dinur and Venkatesan Guruswami: PCPs via low-degree long code and hardness for
constrained hypergraph coloring. In Proc. 54th FOCS, pp. 340โ349. IEEE Comp. Soc., 2013.
[doi:10.1109/FOCS.2013.44] 6
[26] Kashyap Dixit, Madhav Jha, Sofya Raskhodnikova, and Abhradeep Thakurta: Testing the
Lipschitz property over product distributions with applications to data privacy. In Proc.
Theory of Cryptography Conf. (TCCโ13), pp. 418โ436. Springer, 2013. [doi:10.1007/978-3-642-
36594-2_24] 7
[27] Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, and Nithin Varma: Erasure-
resilient property testing. SIAM J. Comput., 47(2):295โ329, 2018. [doi:10.1137/16M1075661]
4, 11
[28] Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, and
Alex Samorodnitsky: Improved testing algorithms for monotonicity. In Proc. 3rd Internat.
Workshop on Randomization and Computation (RANDOMโ99), pp. 97โ108. Springer, 1999.
[doi:10.1007/978-3-540-48413-4_10] 4, 32
[29] Funda Ergรผn, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld, and Mahesh Viswanathan:
Spot-checkers. J. Comput. System Sci., 60(3):717โ751, 2000. [doi:10.1006/jcss.1999.1692] 4, 6
[30] Uriel Feige, Shafi Goldwasser, Lรกszlรณ Lovรกsz, Shmuel Safra, and Mario Szegedy: In-
teractive proofs and the hardness of approximating cliques. J. ACM, 43(2):268โ292, 1996.
[doi:10.1145/226643.226652] 5, 6
[31] Eldar Fischer: On the strength of comparisons in property testing. Inform. Comput.,
189(1):107โ116, 2004. [doi:10.1016/j.ic.2003.09.003] 6
[32] Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, and
Alex Samorodnitsky: Monotonicity testing over general poset domains. In Proc. 34th STOC,
pp. 474โ483. ACM Press, 2002. [doi:10.1145/509907.509977] 4, 7
[33] Katalin Friedl and Madhu Sudan: Some improvements to total degree tests. In
Proc. 3rd Isr. Symp. Theory Comp. Sys. (ISTCSโ95), pp. 190โ198. IEEE Comp. Soc., 1995.
[doi:10.1109/ISTCS.1995.377032] 6
[34] Peter Gemmell, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan, and Avi Wigderson:
Self-testing/correcting for polynomials and for approximate functions. In Proc. 23rd STOC,
pp. 33โ42. ACM Press, 1991. [doi:10.1145/103418.103429] 6
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 43
I DEN K ALEMAJ , S OFYA R ASKHODNIKOVA , AND N ITHIN VARMA
[35] Oded Goldreich: On multiple input problems in property testing. In Proc. 18th Internat.
Workshop on Randomization and Computation (RANDOMโ14), pp. 704โ720. Schloss Dagstuhlโ
Leibniz-Zentrum fuer Informatik, 2014. [doi:10.4230/LIPIcs.APPROX-RANDOM.2014.704]
6
[36] Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, and Alex Samorodnitsky:
Testing monotonicity. Combinatorica, 20(3):301โ337, 2000. [doi:10.1007/s004930070011] 33
[37] Oded Goldreich, Shafi Goldwasser, and Dana Ron: Property testing and its connection to
learning and approximation. J. ACM, 45(4):653โ750, 1998. [doi:10.1145/285055.285060] 3
[38] Venkatesan Guruswami and Atri Rudra: Tolerant locally testable codes. In Proc. 9th
Internat. Workshop on Randomization and Computation (RANDOMโ05), pp. 306โ317. Springer,
2005. [doi:10.1007/11538462_26] 4
[39] Elad Haramaty, Amir Shpilka, and Madhu Sudan: Optimal testing of multivariate polyno-
mials over small prime fields. SIAM J. Comput., 42(2):536โ562, 2013. [doi:10.1137/120879257]
6
[40] Johan Hรฅstad and Avi Wigderson: Simple analysis of graph tests for linearity and PCP.
Random Struct. Algor., 22(2):139โ160, 2003. [doi:10.1002/rsa.10068] 5
[41] Madhav Jha and Sofya Raskhodnikova: Testing and reconstruction of Lipschitz
functions with applications to data privacy. SIAM J. Comput., 42(2):700โ731, 2013.
[doi:10.1137/110840741] 7
[42] Charanjit S. Jutla, Anindya C. Patthak, Atri Rudra, and David Zuckerman: Testing
low-degree polynomials over prime fields. Random Struct. Algor., 35(2):163โ193, 2009.
[doi:10.1002/rsa.20262] 6
[43] Iden Kalemaj, Sofya Raskhodnikova, and Nithin Varma: Sublinear-time computation
in the presence of online erasures. In Proc. 13th Innovations in Theoret. Comp. Sci. Conf.
(ITCSโ22), volume 215, pp. 90:1โ25. Schloss DagstuhlโLeibniz-Zentrum fuer Informatik,
2022. [doi:10.4230/LIPIcs.ITCS.2022.90] 1
[44] Tali Kaufman, Simon Litsyn, and Ning Xie: Breaking the ๐-soundness bound of the linearity
test over GF(2). SIAM J. Comput., 39(5):1988โ2003, 2010. [doi:10.1137/080715548] 5
[45] Tali Kaufman and Dana Ron: Testing polynomials over general fields. SIAM J. Comput.,
36(3):779โ802, 2006. [doi:10.1137/S0097539704445615] 6
[46] Swastik Kopparty and Shubhangi Saraf: Tolerant linearity testing and locally testable
codes. In Proc. 13th Internat. Workshop on Randomization and Computation (RANDOMโ09), pp.
601โ614. Springer, 2009. [doi:10.1007/978-3-642-03685-9_45] 4
[47] Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and Nithin Varma:
Erasure-resilient sublinear-time graph algorithms. ACM Trans. Comput. Theory, 14(1):1โ22,
2021. Preliminary version in ITCSโ21. [doi:10.1145/3488250] 4
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 44
S UBLINEAR -T IME C OMPUTATION IN THE P RESENCE OF O NLINE E RASURES
[48] Alessandro Mantelero: The EU proposal for a general data protection regulation and the
roots of the โright to be forgottenโ. Computer Law & Security Review, 29(3):229โ235, 2013.
[doi:10.1016/j.clsr.2013.03.010] 2
[49] Dana Moshkovitz: Low-degree test with polynomially small error. Comput. Complexity,
26(3):531โ582, 2017. [doi:10.1007/s00037-016-0149-4] 6
[50] Dana Moshkovitz and Ran Raz: Sub-constant error low degree test of almost-linear size.
SIAM J. Comput., 38(1):140โ180, 2008. [doi:10.1137/060656838] 6
[51] Ilan Newman and Nithin Varma: New sublinear algorithms and lower bounds for
LIS estimation. In Proc. 48th Internat. Colloq. on Automata, Languages, and Program-
ming (ICALPโ21), pp. 100:1โ20. Schloss DagstuhlโLeibniz-Zentrum fuer Informatik, 2021.
[doi:10.4230/LIPIcs.ICALP.2021.100] 4
[52] Ryan OโDonnell: Analysis of Boolean Functions. Cambridge Univ. Press, 2014.
[doi:10.1017/CBO9781139814782, arXiv:2105.10386] 12
[53] Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and Nithin Varma: Parame-
terized property testing of functions. ACM Trans. Comput. Theory, 9(4):17:1โ19, 2018.
[doi:10.1145/3155296] 7, 32
[54] Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and Erik Waingarten: Approximat-
ing the distance to monotonicity of boolean functions. Random Struct. Algor., 60(2):233โ260,
2022. [doi:10.1002/rsa.21029] 4
[55] Ramesh Krishnan Pallavoor Suresh: Improved Algorithms and New Models in Property Testing.
Ph. D. thesis, Boston University, 2020. OpenBU. 7
[56] Michal Parnas, Dana Ron, and Ronitt Rubinfeld: Tolerant property testing and distance
approximation. J. Comput. System Sci., 72(6):1012โ1042, 2006. [doi:10.1016/j.jcss.2006.03.002]
4
[57] Sofya Raskhodnikova: Testing if an array is sorted. In Ming-Yang Kao, editor, Encyclopedia
of Algorithms, pp. 2219โ2222. Springer, 2016. [doi:10.1007/978-1-4939-2864-4_700] 6
[58] Sofya Raskhodnikova, Noga Ron-Zewi, and Nithin Varma: Erasures versus errors
in local decoding and property testing. Random Struct. Algor., 59(4):640โ670, 2021.
[doi:10.1002/rsa.21031] 4
[59] Sofya Raskhodnikova and Ronitt Rubinfeld: Linearity testing/Testing Hadamard codes.
In Ming-Yang Kao, editor, Encyclopedia of Algorithms, pp. 1107โ1110. Springer, 2016.
[doi:10.1007/978-1-4939-2864-4_202] 5
[60] Sofya Raskhodnikova and Adam D. Smith: A note on adaptivity in testing properties of
bounded degree graphs. Electron. Colloq. Comput. Complexity, TR06-089, 2006. [ECCC] 39,
40
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 45
I DEN K ALEMAJ , S OFYA R ASKHODNIKOVA , AND N ITHIN VARMA
[61] Sofya Raskhodnikova and Nithin Varma: Brief announcement: Erasure-resilience versus
tolerance to errors. In Proc. 45th Internat. Colloq. on Automata, Languages, and Program-
ming (ICALPโ18), pp. 111:1โ3. Schloss DagstuhlโLeibniz-Zentrum fuer Informatik, 2018.
[doi:10.4230/LIPIcs.ICALP.2018.111] 4
[62] Ran Raz and Shmuel Safra: A sub-constant error-probability low-degree test, and a
sub-constant error-probability PCP characterization of NP. In Proc. 29th STOC, pp. 475โ484.
ACM Press, 1997. [doi:10.1145/258533.258641] 6
[63] Noga Ron-Zewi and Madhu Sudan: A new upper bound on the query complexity
of testing generalized Reed-Muller codes. Theory of Computing, 9(25):783โ807, 2013.
[doi:10.4086/toc.2013.v009a025] 6
[64] Ronitt Rubinfeld and Madhu Sudan: Robust characterizations of polynomials
with applications to program testing. SIAM J. Comput., 25(2):252โ271, 1996.
[doi:10.1137/S0097539793255151] 3, 6
[65] Michael E. Saks and C. Seshadhri: Estimating the longest increasing sequence in polyloga-
rithmic time. SIAM J. Comput., 46(2):774โ823, 2017. [doi:10.1137/130942152] 4
[66] Alex Samorodnitsky: Low-degree tests at large distances. In Proc. 39th STOC, pp. 506โ515.
ACM Press, 2007. [doi:10.1145/1250790.1250864] 5, 6
[67] Alex Samorodnitsky and Luca Trevisan: A PCP characterization of NP with opti-
mal amortized query complexity. In Proc. 32nd STOC, pp. 191โ199. ACM Press, 2000.
[doi:10.1145/335305.335329] 5
[68] Alex Samorodnitsky and Luca Trevisan: Gowers uniformity, influence of variables, and
PCPs. SIAM J. Comput., 39(1):323โ360, 2009. [doi:10.1137/070681612] 5, 6
[69] Amir Shpilka and Avi Wigderson: Derandomizing homomorphism testing in general
groups. SIAM J. Comput., 36(4):1215โ1230, 2006. [doi:10.1137/S009753970444658X] 5
[70] Madhu Sudan and Luca Trevisan: Probabilistically checkable proofs with low amor-
tized query complexity. In Proc. 39th FOCS, pp. 18โ27. IEEE Comp. Soc., 1998.
[doi:10.1109/SFCS.1998.743425] 5
[71] Luca Trevisan: Recycling queries in PCPs and in linearity tests (extended abstract). In Proc.
30th STOC, pp. 299โ308. ACM Press, 1998. [doi:10.1145/276698.276769] 5
[72] Andrew Chi-Chih Yao: Probabilistic computations: Toward a unified measure of com-
plexity (extended abstract). In Proc. 18th FOCS, pp. 222โ227. IEEE Comp. Soc., 1977.
[doi:10.1109/SFCS.1977.24] 38
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 46
S UBLINEAR -T IME C OMPUTATION IN THE P RESENCE OF O NLINE E RASURES
AUTHORS
Iden Kalemaj
Graduate student
Department of Computer Science
Boston University
Boston, MA, USA
ikalemaj bu edu
https://cs-people.bu.edu/ikalemaj/
Sofya Raskhodnikova
Professor
Department of Computer Science
Boston University
Boston, MA, USA
sofya bu edu
https://cs-people.bu.edu/sofya/
Nithin Varma
Assistant Professor
Chennai Mathematical Institute
Chennai, Tamil Nadu, India
nithvarma gmail com
https://www.cmi.ac.in/~nithinvarma/
ABOUT THE AUTHORS
Iden Kalemaj is a Ph. D. student in Computer Science at Boston University, working
under the wonderful supervision of Sofya Raskhodnikova, in the fields of
Sublinear Algorithms and Differential Privacy.
Iden grew up in Vlorรซ, Albania. Her math teacher and school master, Dafina
Brokaj, with a rare sense of humour and wisdom, instilled in Iden the confidence
to pursue mathematics.
Iden completed her undergraduate studies in Mathematics at Princeton Univer-
sity, and started to explore her interest in theoretical computer science via classes
in graph theory and complexity theory. In her free time she enjoys climbing in
the many Boston gyms and taking dance classes.
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 47
I DEN K ALEMAJ , S OFYA R ASKHODNIKOVA , AND N ITHIN VARMA
Sofya Raskhodnikova is a professor of Computer Science at Boston University. Her
office is located in the newly constructed Center for Computing and Data Sciences,
colloquially known as the Jenga building. She received all her degrees (S. B., S. M.,
and Ph. D.) from MIT, and then was a postdoctoral fellow at the Hebrew University
of Jerusalem and the Weizmann Institute of Science. She was a Professor of
Computer Science and Engineering at Penn State and held visiting positions at
the Institute for Pure and Applied Mathematics at UCLA, Boston University,
Harvard University, and at the Simons Institute for the Theory of Computing at
Berkeley. Sofya works in the areas of randomized and approximation algorithms.
Her main interest is the design and analysis of sublinear-time algorithms for
combinatorial problems. She has also made important contributions to data
privacy. Sofya has been a faculty member at Sigma Camp, a residential summer
science camp for kids, for several years. As far as her hobbies go, recall that she
works on privacy.
Nithin Varma is a researcher working in the fields of Sublinear Algorithms and
Approximation Algorithms. He got his Ph. D. from the Computer Science
Department at Boston University, where he was fortunate to be advised by
Sofya Raskhodnikova. After that, he was a postdoctoral researcher at the
Department of Computer Science, University of Haifa, where he was hosted
and mentored by Ilan Newman and Noga Ron-Zewi. He was introduced to
Theoretical Computer Science during his undergraduate years at the Department
of Computer Science and Engineering at the National Institute of Technology
Calicut through the wonderful courses offered by Prof. K Muralikrishnan. In his
free time, Nithin enjoys meditation, singing Indian classical music and practicing
the Mohiniyattam dance.
T HEORY OF C OMPUTING, Volume 19 (1), 2023, pp. 1โ48 48