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

• Published in: arXiv.org 2023-08
• Main Authors: Alrabiah, Omar, Venkatesan Guruswami, Kothari, Pravesh K, Manohar, Peter
• Format: Article
• Language: English
• Subjects: Lower bounds; Polynomials
• ISSN: 2331-8422

A code \(C \colon \{0,1\}^k \to \{0,1\}^n\) is a \(q\)-locally decodable code (\(q\)-LDC) if one can recover any chosen bit \(b_i\) of the message \(b \in \{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 \geq \tilde{\Omega}(k^2)\) on the blocklength. In this paper, we prove a near-cubic lower bound of \(n \geq \tilde{\Omega}(k^3)\) 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 developed in [GKM22, HKM23] and, in particular, relies on bounding the spectral norm of appropriate Kikuchi matrices.