Document Open Access Logo

Brief Announcement: Erasure-Resilience Versus Tolerance to Errors

Authors Sofya Raskhodnikova, Nithin Varma

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.111.pdf
  • Filesize: 249 kB
  • 3 pages

Document Identifiers

Author Details

Sofya Raskhodnikova
  • Boston University, Boston, USA
Nithin Varma
  • Boston University, Boston, USA

Funding

This material is based upon work supported by the National Science Foundation under Grant No. CCF-142297.

Cite AsGet 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)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. 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. Google Scholar
  2. Irit Dinur and Omer Reingold. Assignment testers: Towards a combinatorial proof of the PCP theorem. SIAM J. Comput., 36(4):975-1024, 2006. Google Scholar
  3. Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, and Nithin Varma. Erasure-resilient property testing. SIAM Journal on Computing, 47(2):295-329, 2018. Google Scholar
  4. Eldar Fischer and Lance Fortnow. Tolerant versus intolerant testing for boolean properties. Theory of Computing, 2(9):173-183, 2006. Google Scholar
  5. Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. J. ACM, 45(4):653-750, 1998. Google Scholar
  6. Michal Parnas, Dana Ron, and Ronitt Rubinfeld. Tolerant property testing and distance approximation. J. Comput. Syst. Sci., 72(6):1012-1042, 2006. Google Scholar
  7. Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM J. Comput., 25(2):252-271, 1996. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact