Erasures vs. errors in local decoding and property testing

DOI10.4230/LIPICS.ITCS.2019.63MaRDI QIDQ5090443zbMATH OpenFDO

Authors Sofya Raskhodnikova, Noga Ron-Zewi, Nithin M. Varma

Publication date 18 July 2022

Full work available at URL https://doi.org/10.4230/LIPICS.ITCS.2019.63

zbMATH Keywords

error-correcting codesHadamard codelocal list decodingprobabilistically checkable proofs of proximitytolerant testing

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Randomized algorithms (68W20) Decoding (94B35)

Recommendations

• Erasures versus errors in local decoding and property testing
• Tolerant versus intolerant testing for Boolean properties
• Brief announcement: Erasure-resilience versus tolerance to errors
• Erasure-Resilient Property Testing
• Erasure-resilient property testing

Cites work

• 3-query locally decodable codes of subexponential length
• A Lower Bound on List Size for List Decoding
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
• Bounds for codes in the case of list decoding of finite volume
• Combinatorial PCPs with efficient verifiers
• Combinatorial PCPs with short proofs
• Erasure-Resilient Property Testing
• Highly resilient correctors for polynomials
• scientific article; zbMATH DE number 1306883 (Why is no real title available?)
• Linear-Time Encodable/Decodable Codes With Near-Optimal Rate
• List decoding from erasures: bounds and code constructions
• List-Decoding Algorithms for Lifted Codes
• List-decoding multiplicity codes
• Local list-decoding and testing of random linear codes from high error
• Locally Testable and Locally Correctable Codes Approaching the Gilbert-Varshamov Bound
• Matching vector codes
• Nearly-linear size holographic proofs
• Property testing and its connection to learning and approximation
• Pseudorandom generators without the XOR lemma
• Robust Characterizations of Polynomials with Applications to Program Testing
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Self-testing/correcting with applications to numerical problems
• Some 3CNF Properties Are Hard to Test
• The Complexity of Local List Decoding
• The PCP theorem by gap amplification
• Tolerant property testing and distance approximation
• Tolerant versus intolerant testing for Boolean properties
• Uniform direct product theorems: simplified, optimized, and derandomized

Cited in

(7)

• Erasure-Resilient Property Testing
• Brief announcement: Erasure-resilience versus tolerance to errors
• Erasures versus errors in local decoding and property testing
• Approximating the distance to monotonicity of Boolean functions
• Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate and huge lists)
• Erasure-resilient sublinear-time graph algorithms
• New sublinear algorithms and lower bounds for LIS estimation

This page was built for publication: Erasures vs. errors in local decoding and property testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090443)