Relaxed locally correctable codes with improved parameters

DOI10.4230/LIPICS.ICALP.2021.18MaRDI QIDQ7241114zbMATH OpenFDO

Authors Igor Shinkar

Publication date 12 May 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2021.18

zbMATH Keywords

Reed-Muller coderelaxed locally correctable codesalgorithmic coding theoryrelaxed locally decodable codesconsistency test using random walk

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• scientific article; zbMATH DE number 2019623 (Why is no real title available?)
• scientific article; zbMATH DE number 7650350 (Why is no real title available?)
• 3-query locally decodable codes of subexponential length
• A quadratic lower bound for three-query linear locally decodable codes over any field
• Automata, Languages and Programming
• Boolean function analysis on high-dimensional expanders
• Exponential lower bound for 2-query locally decodable codes via a quantum argument
• High dimensional expanders imply agreement expanders
• High dimensional random walks and colorful expansion
• High order random walks: beyond spectral gap
• Locally decodable codes
• Locally testable codes and PCPs of almost-linear length
• On the efficiency of local decoding procedures for error-correcting codes
• On the power of relaxed local decoding algorithms
• Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity
• Relaxed locally correctable codes
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Towards 3-query locally decodable codes of subexponential length

This page was built for publication: Relaxed locally correctable codes with improved parameters

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