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

A code C : 0, 1 → 0, 1 is a -locally decodable code ( -LDC) if one can recover any chosen bit of the message ∈ 0, 1 with good confidence by randomly querying the encoding ≔ C( ) on at most coordinates. Existing constructions of 2-LDCs achieve = exp( ( )), and lower bounds show that this is in fact tight. However, when = 3, far less is known: the best constructions achieve = exp( (1) ), while the best known results only show a quadratic lower bound ≥ Ω( 2 ) on the blocklength. In this paper, we prove a near-cubic lower bound of ≥ Ω( 3 ) on the blocklength of 3query LDCs. This improves on the best known prior works by a polynomial factor in . 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 developed in [GKM22, HKM23] and, in particular, relies on bounding the spectral norm of appropriate Kikuchi matrices.