Improved Lower Bounds for all Odd-Query Locally Decodable Codes

We prove that for every odd 𝑞 ⩾ 3, any 𝑞-query binary, possibly non-linear locally decodable code (𝑞-LDC) 𝐸 : ±1 𝑘 → ±1 𝑛 must satisfy 𝑘 ⩽ 𝑂(𝑛 1-2/𝑞 ). For even 𝑞, this bound was established in a sequence of works [KT00, GKST06, KW04]. For 𝑞 = 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 𝑞 ⩾ 5.

Our key insight is identifying a general sufficient condition on the hypergraph of local decoding sets called 𝑡-approximate strong regularity. This condition demands that 1) the number of hyperedges containing any given subset of vertices of size 𝑡 (i.e., its co-degree) be equal to the same but arbitrary value 𝑑 𝑡 up to a multiplicative constant slack, and 2) all other co-degrees be upper-bounded relative to 𝑑 𝑡 . 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 𝑡-approximate strong regularity for any 𝑡 ⩽ 𝑞. 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 𝑞-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.