What is the best possible block-length of codes that admit local decoding (i.e., LDCs)?
This question has been puzzling me for more than a couple of decades, and I have recommended a few results regarding it starting with Klim Efremenko's 3-Query Locally Decodable Codes of Subexponential Length (i.e., $n = \exp(k sup o(1))$). The question of whether polynomial lengh (i.e., $n = \poly(k)$) can be achieved for a constant number of queries $q$ is still opened, and the best lower bound is of the form $n = k sup {1+Omega(1/q)}$.
In fact, a lower bound of the form $n = k sup {1+omega(1/q)}$ (i.e., replacing $Omega(1/q)$ by $omega(1/q)$), would be most interesting, because it would prove that relaxed LDCs, introduced in BGHSV04, outperform (standard) LDCs. This is the case since $q$-query relaxed LDC of length $n = k sup {1+O(1/q)}$ are known (see HERE).
The current work does not provide such a result, but it does provide a significant improvement in the case of $q=3$; specifically, it improves the known (almost) quadratic lower bound to an almost cubic one. Note that the new lower bound for $q=3$ is alligned with the state-of-art for even $q$'s (i.e., a lower bound of $n = k sup {(q-o(1))/(q-2)}$). (For larger odd $q$'s the best lower bound is still obtained by looking at $q+1$ queries.)
My impression is that the number of queries used in relaxed LDCs that beat the foregoing lower bound (on the length of 3-query LDC) is at least 10. This is due to the query complexity of a PCP of Proximity (which seems to be invoked with a proximity parameter smaller than $1/8$). It may be time to revisit this problem (of constructing relaxed LDCs).
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 \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.
Available from ECCC TR22-101.