Relaxed locally correctable codes

DOI10.4230/LIPICS.ITCS.2018.27MaRDI QIDQ4993290zbMATH OpenOpenAlexFDO

Authors Tom Gur, Govind Ramnarayan, Ron D. Rothblum

Publication date 15 June 2021

Full work available at URL https://dblp.uni-trier.de/db/conf/innovations/innovations2018.html#GurRR18

zbMATH Keywords

coding theorylocally correctable codesprobabilistically checkable proofs

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Recommendations

• Relaxed locally correctable codes
• Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity
• Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity
• On the power of relaxed local decoding algorithms
• On the power of relaxed local decoding algorithms

Cites work

• scientific article; zbMATH DE number 1306883 (Why is no real title available?)
• 3-query locally decodable codes of subexponential length
• Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
• Combinatorial PCPs with short proofs
• Combinatorial construction of locally testable codes
• Composition of Low-Error 2-Query PCPs Using Decodable PCPs
• Error detecting and error correcting codes
• Local list-decoding and testing of random linear codes from high error
• Locally decodable codes
• Locally testable codes and PCPs of almost-linear length
• Non-interactive proofs of proximity
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Sound 3-query PCPPs are long
• Strong locally testable codes with relaxed local decoders
• Towards 3-query locally decodable codes of subexponential length
• Two-query PCP with subconstant error

Cited in

(15)

• Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity
• Testing distributions of huge objects
• On the power of relaxed local decoding algorithms
• Strong locally testable codes with relaxed local decoders
• Strong locally testable codes with relaxed local decoders
• On the power of relaxed local decoding algorithms
• scientific article; zbMATH DE number 7376033 (Why is no real title available?)
• Smooth and strong PCPs
• Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity
• Local proofs approaching the witness length
• Linear prover IOPs in log star rounds
• Faster sounder succinct arguments and \textsf{IOP}s
• Relaxed locally correctable codes
• Relaxed locally correctable codes with improved parameters
• Proving as fast as computing: succinct arguments with constant prover overhead

This page was built for publication: Relaxed locally correctable codes

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