Theory of Computing
-------------------
Title     : Sublinear-Time Computation in the Presence of Online Erasures
Authors   : Iden Kalemaj, Sofya Raskhodnikova, and Nithin Varma
Volume    : 19
Number    : 1
Pages     : 1-48
URL       : https://theoryofcomputing.org/articles/v019a001

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 $t$ 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 $t$ with
asymptotically the same complexity as in the standard property testing
model. For linearity testing, we prove tight bounds in terms of $t$,
showing that the query complexity is $\Theta(\log t).$ In contrast to
linearity and quadraticity, some other properties, including
sortedness and the Lipschitz property of sequences, cannot be tested
at all, even for $t=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).