Exponential Lower Bounds for 2-query Relaxed Locally Decodable Codes

Alexander R. Block, Jeremiah Blocki, Kuan Cheng +4

Locally Decodable Codes (LDCs) are error-correcting codes $C:\hat{I}{\pounds }^n\to \hat{I}{\pounds }^m,$ encoding \emph{messages} in $\hat{I}{\pounds }^n$ to \emph{codewords} in $\hat{I}{\pounds }^m$, with super-fast decoding…