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

A code C ∶ 0,1k → 0,1n is a q-locally decodable code (q-LDC) if one can recover any chosen bit bi of the message b ∈ 0,1k 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(ko(1)), while the best known results only show a quadratic lower bound n ≥ Ω(k2/log(k)) on the blocklength.