Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR11-154 | 17th November 2011 21:09

#### From Irreducible Representations to Locally Decodable Codes

TR11-154
Authors: Klim Efremenko
Publication: 18th November 2011 04:20
Keywords:

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.

ISSN 1433-8092 | Imprint