Dixit, Kashyap ;
Raskhodnikova, Sofya ;
Thakurta, Abhradeep ;
Varma, Nithin
ErasureResilient Property Testing
Abstract
Property testers form an important class of sublinear algorithms. In the standard property testing model, an algorithm accesses the input function f:D > R via an oracle. With very few exceptions, all property testers studied in this model rely on the oracle to provide function values at all queried domain points. However, in many realistic situations, the oracle may be unable to reveal the function values at some domain points due to privacy concerns, or when some of the values get erased by mistake or by an adversary. The testers do not learn anything useful about the property by querying those erased points. Moreover, the knowledge of a tester may enable an adversary to erase some of the values so as to increase the query complexity of the tester arbitrarily or, in some cases, make the tester entirely useless.
In this work, we initiate a study of property testers that are resilient to the presence of adversarially erased function values. An alphaerasureresilient epsilontester is given parameters alpha, epsilon in (0,1), along with oracle access to a function f such that at most an alpha fraction of function values have been erased. The tester does not know whether a value is erased until it queries the corresponding domain point. The tester has to accept with high probability if there is a way to assign values to the erased points such that the resulting function satisfies the desired property P. It has to reject with high probability if, for every assignment of values to the erased points, the resulting function has to be changed in at least an epsilonfraction of the nonerased domain points to satisfy P.
We design erasureresilient property testers for a large class of properties. For some properties, it is possible to obtain erasureresilient testers by simply using standard testers as a black box. However, there are more challenging properties for which all known testers rely on querying a specific point. If this point is erased, all these testers break. We give efficient erasureresilient testers for several important classes of such properties of functions including monotonicity, the Lipschitz property, and convexity. Finally, we show a separation between the standard testing and erasureresilient testing. Specifically, we describe a property that can be epsilontested with O(1/epsilon) queries in the standard model, whereas testing it in the erasureresilient model requires number of queries polynomial in the input size.
BibTeX  Entry
@InProceedings{dixit_et_al:LIPIcs:2016:6194,
author = {Kashyap Dixit and Sofya Raskhodnikova and Abhradeep Thakurta and Nithin Varma},
title = {{ErasureResilient Property Testing}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {91:191:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770132},
ISSN = {18688969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6194},
URN = {urn:nbn:de:0030drops61947},
doi = {10.4230/LIPIcs.ICALP.2016.91},
annote = {Keywords: Randomized algorithms, property testing, error correction, monotoneand Lipschitz functions}
}
23.08.2016
Keywords: 

Randomized algorithms, property testing, error correction, monotoneand Lipschitz functions 
Seminar: 

43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Issue date: 

2016 
Date of publication: 

23.08.2016 