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

A code C:{0,1}k→{0,1}n is a q-query locally decodable code (q-LDC) if one can recover any chosen bit bi of the message b∈{0,1}k with good confidence by querying a corrupted string x~ of the codeword x=C(b) in at most q coordinates. For 2 queries, the Hadamard code is a 2-LDC of length n=2k, and this code is in fact essentially optimal [1], [2]. For q≥3, there is a large gap in our understanding: the best constructions achieve n=exp(ko(1)), while prior to the recent work of [3], the best lower bounds were n≥Ω~(kqq−2) for q even and n≥Ω~(kq+1q−1) for q odd. The recent work of [3] used techniques from semirandom XOR refutation to prove a lower bound of n≥Ω~(k3) for q = 3, thus achieving the “ kqq−2 bound” for an odd value of q. However, their proof does not extend to any odd q≥5. In this paper, we prove a q-LDC lower bound of n≥Ω~(kqq−2) 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.