__
TR11-154 | 17th November 2011 21:09
__

#### From Irreducible Representations to Locally Decodable Codes

**Abstract:**
Locally 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.