A kq/q-2 Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs

A code $\mathcal{C}:\{0,1\}^{k} \rightarrow\{0,1\}^{n}$ is a q-query 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 querying a corrupted string $\tilde{x}$ of the codeword $x=\mathcal{C}(b)$ in at most q coordinates. For 2 queries, the Hadamard code is a 2-LDC of length $n=2^{k}$, and this code is in fact essentially optimal [1], [2]. For $q \geq 3$, there is a large gap in our understanding: the best constructions achieve $n=\exp \left(k^{o(1)}\right)$, while prior to the recent work of [3], the best lower bounds were $n \geq \tilde{\Omega}\left(k^{\frac{q}{q-2}}\right)$ for q even and $n \geq \tilde{\Omega}\left(k^{\frac{q+1}{q-1}}\right)$ for q odd. The recent work of [3] used techniques from semirandom XOR refutation to prove a lower bound of $n \geq \tilde{\Omega}\left(k^{3}\right)$ for q = 3, thus achieving the “ $k^{\frac{q}{q-2}}$ bound” for an odd value of q. However, their proof does not extend to any odd $q \geq 5$. In this paper, we prove a q-LDC lower bound of $n \geq \tilde{\Omega}\left(k^{\frac{q}{q-2}}\right)$ for any odd q. Our key technical idea is the use of an imbalanced bipartite Kikuchi graph, which gives a simpler method to analyze spectral refutations of odd arity XOR without using the standard “Cauchy-Schwarz trick” ― a trick that typically produces random matrices with nontrivially correlated entries and makes the analysis for odd arity XOR significantly more complicated than even arity XOR.