Improved Lower Bounds for all Odd-Query Locally Decodable Codes

We prove that for every odd q ≥ 3, any q-query binary, possibly non-linear locally decodable code (q-LDC) E : ±1^k → ±1ⁿ must satisfy k ≤ Õ(n^1-2/q). For even q, this bound was established in a sequence of works [KT00], [GKST06], [KW04]. For q = 3, the above bound was achieved in a recent work [AGKM23] using an argument that crucially exploits known exponential lower bounds for 2-LDCs. Their strategy hits an inherent bottleneck for q ≥ 5.Our key insight is identifying a general sufficient condition on the hypergraph of local decoding sets called t-approximate strong regularity. This condition demands that 1) the number of hyperedges containing any given subset of vertices of size t (i.e., its co-degree) be equal to the same but arbitrary value d_t up to a multiplicative constant slack, and 2) all other co-degrees be upper-bounded relative to d_t. This condition significantly generalizes related proposals in prior works [GKM22], [HKM23], [AGKM23], [HKM⁺24] that demand absolute upper bounds on all co-degrees.We give an argument based on spectral bounds on Kikuchi Matrices that lower bounds the blocklength of any LDC whose local decoding sets satisfy t-approximate strong regularity for any t ≤ q. Crucially, unlike prior works, our argument works despite having no non-trivial absolute upper bound on the co-degrees of any set of vertices. To apply our argument to arbitrary q-LDCs, we give a new, greedy, approximate strong regularity decomposition that shows that arbitrary, dense enough hypergraphs can be partitioned (up to a small error) into approximately strongly regular pieces satisfying the required relative bounds on the co-degrees.