A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation
Omar Alrabiah, Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar
Abstract
A code C ∶ {0,1}k → {0,1}n is a q-locally decodable code (q-LDC) if one can recover any chosen bit bi 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(ko(1)), while the best known results only show a quadratic lower bound n ≥ Ω(k2/log(k)) on the blocklength.
Topics & Concepts
Quadratic equationUpper and lower boundsCode (set theory)CombinatoricsEncoding (memory)MathematicsDiscrete mathematicsComputer scienceSet (abstract data type)GeometryProgramming languageMathematical analysisArtificial intelligenceCryptography and Data SecurityComplexity and Algorithms in GraphsCooperative Communication and Network Coding