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} n 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.

Authors

• Arpon Basu
• Jun-Ting Hsieh
• Pravesh K. Kothari
• Andrew D. Lin

Keywords

• Computer science
• Lower bound
• Sufficient conditions
• Upper bound
• Codes
• Decoding
• Proposals
• Decodable Codes
• General Condition
• Strong Regularity
• Subset Of Vertices
• Cardinality
• Loss Of Generality
• Proof Of Theorem
• Average Degree
• Even Number
• Conditions Of Theorem
• L1-norm
• Codeword
• Monomial
• After Dropping
• Query Set
• Spectral Norm
• Message Length
• Inequality In Theorem
• Peeling Off
• Decoding Algorithm
• even covers
• kikuchi matrices
• ldc lower bounds
• locally decodable codes