DIMACS Theoretical Computer Science Seminar

Title: From Irreducible Representations to Locally Decodable Codes

Speaker: Klim Efremenko, Tel-Aviv University

Date: Wednesday, September 19, 2012 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ


A q-query Locally Decodable Code (LDC) is an error-correcting code that allows reading any particular symbol of the message by reading only q symbols of the codeword.

In this talk we present a new approach for the construction of LDCs from representation theory. We show that if there exists an irreducible representation (\rho, V) of the 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 will show that both matching vector codes and Reed-Muller codes fall in this framework.

No prior knowledge in representation theory will be assumed.

See: http://www.cs.rutgers.edu/~allender/theory-fall12.html