Loading...
Please wait, while we are loading the content...
Similar Documents
Erasure-Resilient Property Testing
| Content Provider | Society for Industrial and Applied Mathematics (SIAM) |
|---|---|
| Author | Raskhodnikova, Sofya Dixit, Kashyap Varma, Nithin Thakurta, Abhradeep |
| Copyright Year | 2018 |
| Abstract | Property testers form an important class of sublinear-time algorithms. In the standard property testing model, an algorithm accesses the input function $f :\mathcal{D} \mapsto {\cal 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 function 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 $\alpha$-erasure-resilient $\varepsilon$-tester is given parameters $\alpha \in [0,1),\varepsilon\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 $\mathcal{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 $\varepsilon$ fraction of the nonerased domain points to satisfy $\mathcal{P}$. Erasure-resilient testing generalizes the standard property testing model of Rubinfeld and Sudan [SIAM J. Comput., 25 (1996), pp. 252--271] and Goldreich, Goldwasser, and Ron [J. ACM, 45 (1998), pp. 653--750]. Compared to the tolerant testing model of Parnas, Ron, and Rubinfeld [J. Comput. System Sci., 6 (2006), pp. 1012--1042], our model places less stringent requirements on the tester. We design erasure-resilient property testers for a large class of properties. For some properties, it is possible to obtain erasure-resilient testers by simply using standard testers as a black box. However, for some more challenging properties, all existing algorithms are more likely to query certain points in the domain. If these points are erased, the algorithms break. We give efficient erasure-resilient 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 and erasure-resilient testing. Specifically, we describe a property that can be $\varepsilon$-tested with $O(1/\varepsilon)$ queries in the standard model, whereas testing it in the erasure-resilient model requires a number of queries polynomial in the input size. |
| Sponsorship | Pennsylvania State University. National Science Foundation |
| Starting Page | 295 |
| Ending Page | 329 |
| Page Count | 35 |
| File Format | |
| ISSN | 00975397 |
| DOI | 10.1137/16M1075661 |
| e-ISSN | 10957111 |
| Journal | SIAM Journal on Computing (SMJCAT) |
| Issue Number | 2 |
| Volume Number | 47 |
| Language | English |
| Publisher | Society for Industrial and Applied Mathematics |
| Publisher Date | 2018-03-06 |
| Access Restriction | Subscribed |
| Subject Keyword | sublinear algorithms Probability in computer science convex and Lipschitz functions Randomized algorithms Approximation algorithms Searching and sorting property testing Analysis of algorithms monotone error correction |
| Content Type | Text |
| Resource Type | Article |
| Subject | Mathematics Computer Science |
