scientific article; zbMATH DE number 7559106

DOI10.4230/LIPIcs.ITCS.2019.63zbMath1502.68365MaRDI QIDQ5090443

Noga Ron-Zewi, Sofya Raskhodnikova, Nithin Varma

Publication date: 18 July 2022

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

error-correcting codesHadamard codeprobabilistically checkable proofs of proximitytolerant testinglocal list decoding

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)

Related Items

Erasures versus errors in local decoding and property testing, Approximating the distance to monotonicity of Boolean functions

Cites Work

• Unnamed Item
• Unnamed Item
• Combinatorial PCPs with short proofs
• Combinatorial PCPs with efficient verifiers
• Bounds for codes in the case of list decoding of finite volume
• Highly resilient correctors for polynomials
• Self-testing/correcting with applications to numerical problems
• Tolerant property testing and distance approximation
• Nearly-linear size holographic proofs
• Local List-Decoding and Testing of Random Linear Codes from High Error
• Some remarks on multiplicity codes
• List-Decoding Algorithms for Lifted Codes
• Matching Vector Codes
• Property testing and its connection to learning and approximation
• The Complexity of Local List Decoding
• List decoding from erasures: bounds and code constructions
• Linear-Time Encodable/Decodable Codes With Near-Optimal Rate
• Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized
• Locally Testable and Locally Correctable Codes Approaching the Gilbert-Varshamov Bound
• Erasure-Resilient Property Testing
• High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query Complexity
• Robust Characterizations of Polynomials with Applications to Program Testing
• 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
• Some 3CNF Properties Are Hard to Test
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
• The PCP theorem by gap amplification
• Pseudorandom generators without the XOR lemma