ECCC-Report TR22-101https://eccc.weizmann.ac.il/report/2022/101Comments and Revisions published for TR22-101en-usTue, 29 Aug 2023 18:30:41 +0300
Revision 1
| A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation |
Omar Alrabiah,
Pravesh Kothari,
Venkatesan Guruswami,
Peter Manohar
https://eccc.weizmann.ac.il/report/2022/101#revision1A 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 $(\infty \to 1)$-norm of appropriate Kikuchi matrices.Tue, 29 Aug 2023 18:30:41 +0300https://eccc.weizmann.ac.il/report/2022/101#revision1
Paper TR22-101
| A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation |
Omar Alrabiah,
Pravesh Kothari,
Venkatesan Guruswami,
Peter Manohar
https://eccc.weizmann.ac.il/report/2022/101A 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 \widetilde{\Omega}(k^2)$ on the blocklength.
In this paper, we prove a near-cubic lower bound of $n \geq \widetilde{\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] and, in particular, relies on bounding the $(\infty \to 1)$-norm of appropriate Kikuchi matrices.Fri, 15 Jul 2022 00:14:52 +0300https://eccc.weizmann.ac.il/report/2022/101