2024/11/21 by Oliver Janzer, Janzer, Oliver, Peter Manohar +1 · 2 citations
Computer Science · #Coding theory and cryptography #Cooperative Communication and Network Coding
paper · pdf · doi:10.48550/arxiv.2411.14276
A code C \colon \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. 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 [AGKM23], the best lower bounds were n ≥ Ω(k(q)/(q-2)) for q even and n ≥ Ω(k(q+1)/(q-1)) for q odd. The recent work of [AGKM23] used techniques from semirandom XOR refutation to prove a lower bound of n ≥ Ω(k3) for q = 3, thus achieving the "k(q)/(q-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 ≥ Ω(k(q)/(q-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.