Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR11-154 | 17th November 2011 21:09

From Irreducible Representations to Locally Decodable Codes

RSS-Feed




TR11-154
Authors: Klim Efremenko
Publication: 18th November 2011 04:20
Downloads: 2108
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