Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: From Irreducible Representations to Locally Decodable Codes
event speaker icon
Klim Efremenko (Tel-Aviv University)
event date icon
Wednesday, 20.06.2012, 12:30
event location icon
Taub 201
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 talk we will show connection between LDC and a representation theory. We show that if there exists an irreducible representation (\rho, V) of a group G and q elements g_1,g_2,..., 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-> 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.

No prior knowledge in representation theory will be assumed.