  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.
