Erasures versus errors in local decoding and property testing. Issue 4 (7th July 2021)

• Record Type: Journal Article
• Authors: Raskhodnikova, Sofya; Ron‐Zewi, Noga; Varma, Nithin
• Is Part Of: Random structures & algorithms. Volume 59:Issue 4(2021)
• Page Start: 640
• Page End: 670
• Publication Date: 2021-07-07
• Subjects: erasures versus errors -- Goldreich–Levin theorem -- Hadamard code -- local decoding -- property testing; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21031
• Languages: English
• ISSNs: 1042-9832

Abstract

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. We first investigate 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, arbitrarily close to 1, with list sizes and query complexity better than in the Goldreich–Levin theorem. We further study approximate locally erasure list‐decodable codes and use them to construct a property that is erasure‐resiliently testable with query complexity independent of the input length, n, but requires n Ω ( 1 ) queries for tolerant testing. We also investigate the general relationship between local decoding in the presence of errors and in the presence of erasures.