Sublinear-time computation in the presence of online erasures
Files
Published version
Date
2022-01-31
Authors
Kalemaj, Iden
Raskhodnikova, Sofya
Varma, Nithin
Version
OA Version
Published version
Citation
I. Kalemaj, S. Raskhodnikova, N. Varma. 2022. "Sublinear-Time Computation in the Presence of Online Erasures" https://doi.org/10.4230/LIPIcs.ITCS.2022.90
Abstract
We initiate the study of sublinear-time algorithms that access their input via an online adversarial
erasure oracle. After answering each query to the input object, 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
Θ(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.
Description
License
© Iden Kalemaj, Sofya Raskhodnikova, and Nithin Varma; licensed under Creative Commons License CC-BY 4.0