A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation

Omar Alrabiah, Venkatesan Guruswami, Pravesh K. Kothari +1

A code $C:\{0,1{\}}^k\to \{0,1{\}}^n$ is a $q$-locally decodable code ($q$-LDC) if one can recover any chosen bit $b_i$ of the message $b\in \{0,1{\}}^k$ with good confidence by…