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:{\Sigma }^n\to {\Sigma }^m,$ encoding \emph{messages} in ${\Sigma }^n$ to \emph{codewords} in ${\Sigma }^m$, with super-fast decoding algo…