A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation

A code C ∶ {0,1} k → {0,1} n is a q -locally decodable code ( q -LDC) if one can recover any chosen bit b i of the message b ∈ {0,1} k with good confidence by randomly querying the encoding x = C ( b ) on at most q coordinates. Existing constructions of 2-LDCs achieve n = exp( O ( k )), and lower bounds show that this is in fact tight. However, when q = 3, far less is known: the best constructions achieve n = exp( k o (1) ), while the best known results only show a quadratic lower bound n ≥ Ω( k 2 /log( k )) on the blocklength. In this paper, we prove a near-cubic lower bound of n ≥ Ω( k 3 /log 6 ( k )) on the blocklength of 3-query LDCs. This improves on the best known prior works by a polynomial factor in k . Our proof relies on a new connection between LDCs and refuting constraint satisfaction problems with limited randomness. Our quantitative improvement builds on the new techniques for refuting semirandom instances of CSPs and, in particular, relies on bounding the spectral norm of appropriate Kikuchi matrices.

Authors

• Omar Alrabiah
• Venkatesan Guruswami
• Pravesh K. Kothari
• Peter Manohar

Keywords

• CSP refutation
• Locally decodable codes