Document Open Access Logo

Erasures vs. Errors in Local Decoding and Property Testing

Authors Sofya Raskhodnikova, Noga Ron-Zewi, Nithin Varma

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2019.63.pdf
  • Filesize: 0.51 MB
  • 21 pages

Document Identifiers

Author Details

Sofya Raskhodnikova
  • Department of Computer Science, Boston University, USA
Noga Ron-Zewi
  • Department of Computer Science, University of Haifa, Israel
Nithin Varma
  • Department of Computer Science, Boston University, USA

Funding

The first and the third author were supported by National Science Foundation under Grant No. CCF-142297.

Cite As Get BibTex

Sofya Raskhodnikova, Noga Ron-Zewi, and Nithin Varma. Erasures vs. Errors in Local Decoding and Property Testing. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 63:1-63:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ITCS.2019.63

Abstract

We initiate the study of the role of erasures in local decoding and use our understanding to prove a separation between erasure-resilient and tolerant property testing. Local decoding in the presence of errors has been extensively studied, but has not been considered explicitly in the presence of erasures.
Motivated by applications in property testing, we begin our investigation with local list decoding in the presence of erasures. We prove an analog of a famous result of Goldreich and Levin on local list decodability of the Hadamard code. Specifically, we show that the Hadamard code is locally list decodable in the presence of a constant fraction of erasures, arbitrary close to 1, with list sizes and query complexity better than in the Goldreich-Levin theorem. We use this result to exhibit a property which is testable with a number of queries independent of the length of the input in the presence of erasures, but requires a number of queries that depends on the input length, n, for tolerant testing. We further study approximate locally list decodable codes that work against erasures and use them to strengthen our separation by constructing a property which is testable with a constant number of queries in the presence of erasures, but requires n^{Omega(1)} queries for tolerant testing.
Next, we study the general relationship between local decoding in the presence of errors and in the presence of erasures. We observe that every locally (uniquely or list) decodable code that works in the presence of errors also works in the presence of twice as many erasures (with the same parameters up to constant factors). We show that there is also an implication in the other direction for locally decodable codes (with unique decoding): specifically, that the existence of a locally decodable code that works in the presence of erasures implies the existence of a locally decodable code that works in the presence of errors and has related parameters. However, it remains open whether there is an implication in the other direction for locally list decodable codes. We relate this question to other open questions in local decoding.

Subject Classification

ACM Subject Classification
  • Theory of computation → Streaming, sublinear and near linear time algorithms
  • Mathematics of computing → Coding theory
Keywords
  • Error-correcting codes
  • probabilistically checkable proofs (PCPs) of proximity
  • Hadamard code
  • local list decoding
  • tolerant testing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Noga Alon, Jeff Edmonds, and Michael Luby. Linear Time Erasure Codes with Nearly Optimal Recovery. In Proceedings of FOCS 1995, pages 512-519, 1995. Google Scholar
  2. László Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy. Checking Computations in Polylogarithmic Time. In Proceedings of STOC 1991, pages 21-31, 1991. Google Scholar
  3. Amos Beimel, Yuval Ishai, Eyal Kushilevitz, and Jean-Francois Raymond. Breaking the O(n^1/(2k-1)) Barrier for Information-Theoretic Private Information Retrieval. In Proceedings of FOCS 2002, pages 261-270, 2002. Google Scholar
  4. Avraham Ben-Aroya, Klim Efremenko, and Amnon Ta-Shma. A Note on Amplifying the Error-Tolerance of Locally Decodable Codes. Electronic Colloquium on Computational Complexity (ECCC), 17:134, 2010. Google Scholar
  5. Avraham Ben-Aroya, Klim Efremenko, and Amnon Ta-Shma. Local List Decoding with a Constant Number of Queries. In Proceedings of FOCS 2010, pages 715-722, 2010. Google Scholar
  6. 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
  7. Eli Ben-Sasson, Prahladh Harsha, and Sofya Raskhodnikova. Some 3CNF Properties Are Hard to Test. SIAM J. Comput., 35(1):1-21, 2005. Google Scholar
  8. Volodia M. Blinovsky. Bounds for codes in the case of list decoding of finite volume. Problems of Information Transmission, 22(1):7-19, 1986. Google Scholar
  9. Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-Testing/Correcting with Applications to Numerical Problems. J. of Computer and System Sciences, 47(3):549-595, 1993. Google Scholar
  10. Irit Dinur. The PCP theorem by gap amplification. J. ACM, 54(3):12, 2007. Google Scholar
  11. 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
  12. Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, and Nithin M. Varma. Erasure-Resilient Property Testing. SIAM J. Comput., 47(2):295-329, 2018. Google Scholar
  13. Zeev Dvir, Parikshit Gopalan, and Sergey Yekhanin. Matching Vector Codes. SIAM J. Comput., 40(4):1154-1178, 2011. Google Scholar
  14. Klim Efremenko. 3-Query Locally Decodable Codes of Subexponential Length. SIAM J. on Computing, 41(6):1694-1703, 2012. Google Scholar
  15. Eldar Fischer and Lance Fortnow. Tolerant Versus Intolerant Testing for Boolean Properties. Theory of Computing, 2(9):173-183, 2006. Google Scholar
  16. Peter Gemmell, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan, and Avi Wigderson. Self-testing/correcting for polynomials and for approximate functions. In Proceedings of STOC 1991, pages 32-42, 1991. Google Scholar
  17. Peter Gemmell and Madhu Sudan. Highly resilient correctors for polynomials. Information Processing Letters, 43(4):169-174, 1992. Google Scholar
  18. 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
  19. Oded Goldreich and Leonid A. Levin. A Hard-Core Predicate for all One-Way Functions. In Proceedings of STOC 1989, pages 25-32, 1989. Google Scholar
  20. Sivakanth Gopi, Swastik Kopparty, Rafael Mendes de Oliveira, Noga Ron-Zewi, and Shubhangi Saraf. Locally Testable and Locally Correctable Codes Approaching the Gilbert-Varshamov Bound. In Proceedings of SODA 2017, pages 2073-2091, 2017. Google Scholar
  21. Aryeh Grinberg, Ronen Shaltiel, and Emanuele Viola. Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs. In FOCS, 2018. URL: https://eccc.weizmann.ac.il/report/2018/061.
  22. Alan Guo and Swastik Kopparty. List-Decoding Algorithms for Lifted Codes. IEEE Trans. Information Theory, 62(5):2719-2725, 2016. Google Scholar
  23. Venkatesan Guruswami. List decoding from erasures: bounds and code constructions. IEEE Trans. Information Theory, 49(11):2826-2833, 2003. Google Scholar
  24. Venkatesan Guruswami and Piotr Indyk. Linear-time encodable/decodable codes with near-optimal rate. IEEE Trans. Information Theory, 51(10):3393-3400, 2005. Google Scholar
  25. Venkatesan Guruswami and Atri Rudra. Tolerant Locally Testable Codes. In Proceedings of RANDOM 2005, pages 306-317, 2005. Google Scholar
  26. Venkatesan Guruswami and Salil P. Vadhan. A Lower Bound on List Size for List Decoding. IEEE Trans. Information Theory, 56(11):5681-5688, 2010. Google Scholar
  27. Dan Gutfreund and Guy N. Rothblum. The Complexity of Local List Decoding. In Proceedings of RANDOM 2008, pages 455-468, 2008. Google Scholar
  28. Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, and Avi Wigderson. Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized. SIAM J. Comput., 39(4):1637-1665, 2010. Google Scholar
  29. Swastik Kopparty. List-Decoding Multiplicity Codes. Theory of Comput., 11:149-182, 2015. Google Scholar
  30. Swastik Kopparty, Or Meir, Noga Ron-Zewi, and Shubhangi Saraf. High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query Complexity. J. ACM, 64(2):11:1-11:42, 2017. Google Scholar
  31. Swastik Kopparty and Shubhangi Saraf. Local List-Decoding and Testing of Random Linear Codes from High Error. SIAM J. Comput., 42(3):1302-1326, 2013. Google Scholar
  32. Or Meir. Combinatorial PCPs with Efficient Verifiers. Comp. Complexity, 23(3):355-478, 2014. Google Scholar
  33. Or Meir. Combinatorial PCPs with Short Proofs. Comp. Complexity, 25(1):1-102, 2016. Google Scholar
  34. Michal Parnas, Dana Ron, and Ronitt Rubinfeld. Tolerant property testing and distance approximation. J. Comput. Syst. Sci., 72(6):1012-1042, 2006. Google Scholar
  35. Alexander Polishchuk and Daniel A. Spielman. Nearly-linear size holographic proofs. In Proceedings of STOC 1994, pages 194-203. ACM Press, 1994. Google Scholar
  36. Sofya Raskhodnikova, Noga Ron-Zewi, and Nithin Varma. Erasures versus Errors in Local Decoding and Property Testing. Electronic Colloquium on Computational Complexity (ECCC), 2018. URL: https://eccc.weizmann.ac.il/report/2018/195.
  37. Ronitt Rubinfeld and Madhu Sudan. Robust Characterizations of Polynomials with Applications to Program Testing. SIAM J. Comput., 25(2):252-271, 1996. Google Scholar
  38. Madhu Sudan, Luca Trevisan, and Salil P. Vadhan. Pseudorandom Generators without the XOR Lemma. J. Comput. Syst. Sci., 62(2):236-266, 2001. Google Scholar
  39. Luca Trevisan. Some Applications of Coding Theory in Computational Complexity. CoRR, cs.CC/0409044, 2004. URL: http://arxiv.org/abs/cs/0409044.
  40. Sergey Yekhanin. Towards 3-query locally decodable codes of subexponential length. J. of the ACM, 55(1):1:1-1:16, 2008. 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 About DROPS Imprint Privacy Contact