A large alphabet Locally Decodable Code (LDC) $C:\Sigma^{k} \to \Sigma'^{n}$, where $\Sigma'$ may be large, is a code where each symbol of $x$ can be decoded by making few queries to a noisy version of $C(x)$. The rate of $C$ is its information rate, namely $\frac{k \log (|\Sigma|) }{n \log (|\Sigma'|)}$. We construct the first constant-rate large alphabet LDC $C$ making a polylogarithmic number of queries (in $k$ and $n$), while satisfying $\log |\Sigma'| \leq k^{\eps}$ for any chosen constant $\eps < 1$. We add that in fact we show a code with a property stronger than being a large alphabet LDC, which we dub \emph{block-wise Locally Correctable Code (block-wise LCC)}, implying LDC.

Our construction is a variant of multivariate Multiplicity codes which were introduced in the seminal work of Kopparty, Saraf and Yekhanin (STOC '11). However we remark that our definition of the code and its analysis are taking a somewhat different approach, considering specific linear relations that are required for our purposes. While the resulting rate is akin to the one obtained through standard multiplicity codes analysis, this dual-based analysis extends to other families of linear-constraint codes of the same flavor and may be of independent technical interest.

To get the polylogarithmic query complexity we observe a correction process for which very few random lines suffice in order to correct an element, as opposed to an exponential number of lines as is usually required in decoding Multiplicity codes. This seems to be the first non-trivial case where the lower-bound for LDC due to Katz and Trevisan (STOC '00), which in particular implies that for constant rate the number of queries is at least logarithmic in the code's length, is close to tight.