LIPIcs.ICALP.2018.111.pdf
- Filesize: 249 kB
- 3 pages
Document
Brief Announcement: Erasure-Resilience Versus Tolerance to Errors
Authors
-
Part of:
Volume:
45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Colloquium on Automata, Languages, and Programming (ICALP) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-07-04
Cite As Get BibTex
Sofya Raskhodnikova and Nithin Varma. Brief Announcement: Erasure-Resilience Versus Tolerance to Errors. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 111:1-111:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.111
Abstract
We describe work in progress on providing a separation between erasure-resilient and tolerant property testing. Specifically, we are able to exhibit a property which is testable (with the number of queries independent of the length of the input) in the presence of erasures, but is not testable tolerantly.
Subject Classification
ACM Subject Classification
- Theory of computation → Streaming, sublinear and near linear time algorithms
Keywords
- Property testing
- erasures
- tolerance to errors
- model separation
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil P. Vadhan. Robust PCPs of proximity, shorter PCPs, and applications to coding. SIAM J. Comput., 36(4):889-974, 2006.
-
Irit Dinur and Omer Reingold. Assignment testers: Towards a combinatorial proof of the PCP theorem. SIAM J. Comput., 36(4):975-1024, 2006.
-
Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, and Nithin Varma. Erasure-resilient property testing. SIAM Journal on Computing, 47(2):295-329, 2018.
-
Eldar Fischer and Lance Fortnow. Tolerant versus intolerant testing for boolean properties. Theory of Computing, 2(9):173-183, 2006.
-
Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. J. ACM, 45(4):653-750, 1998.
-
Michal Parnas, Dana Ron, and Ronitt Rubinfeld. Tolerant property testing and distance approximation. J. Comput. Syst. Sci., 72(6):1012-1042, 2006.
-
Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM J. Comput., 25(2):252-271, 1996.