Improved Lower Bounds for all Odd-Query Locally Decodable Codes

Arpon Basu, Jun-Ting Hsieh, Pravesh K. Kothari +1

We prove that for every odd $q\ge 3$, any $q$-query binary, possibly non-linear locally decodable code ($q$-LDC) $E:\{\pm 1{\}}^k\to \{\pm 1{\}}^n$ must satisfy $k \leq \tilde{…