Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes

Elena Grigorescu, Vinayak M. Kumar, Peter Manohar +1

A locally decodable code (LDC) $C:\{0,1{\}}^k\to \{0,1{\}}^n$ is an error-correcting code that allows one to recover any bit of the original message with good probability while…