ECCC-Report TR11-154https://eccc.weizmann.ac.il/report/2011/154Comments and Revisions published for TR11-154en-usFri, 18 Nov 2011 04:20:05 +0200
Paper TR11-154
| From Irreducible Representations to Locally Decodable Codes |
Klim Efremenko
https://eccc.weizmann.ac.il/report/2011/154Locally Decodable Code (LDC) is a code that encodes a message in a way that one can decode any particular symbol of the message by reading only a constant number of locations, even if a constant fraction of the encoded message is adversarially
corrupted.
In this paper we present a new approach for the construction of LDCs. We show that if there exists an irreducible representation $(\rho, V)$ of $G$ and $q$ elements $g_1,g_2,\ldots, g_q$
in $G$ such that there exists a linear combination of matrices $\rho(g_i)$ that is of rank one,
then we can construct a $q$-query Locally Decodable Code
$C:V\rightarrow \F^G$.
We show the potential of this approach by constructing constant query LDCs of sub-exponential length matching the parameters of the best known constructions.Fri, 18 Nov 2011 04:20:05 +0200https://eccc.weizmann.ac.il/report/2011/154