From Irreducible Representations to Locally Decodable Codes

摘要

A q-query Locally Decodable Code (LDC) is an error correcting code that allows to read any particular symbol of the message by reading only q symbols of the codeword even if the codeword is adversary corrupted. In this paper we present a new approach for the construction of LDCs. We show that if there exists an irreducible representation (p, V) of G and q elements g_1, g_2, ···, g_q in G such that there exists a linear combination of matrices ρ(g_i) that is of rank one, then we can construct a q-query Locally Decodable Code C : V → F~G. We show the potential of this approach by constructing constant query LDCs of sub-exponential length matching the best known constructions.