Abstract: Locally Decodable Codes(LDC) are a class of Error Correcting Codes. Error Correcting Codes allow us to encode a message to a codeword in such a way that even if a certain fraction of a codeword is corrupted by an evil adversary one will still be able to recover the message. What happens if someone needs only one bit from a message? In general, to recover a single bit one will need to read the whole codeword and decode it. The question is, whether it is possible to do something better.

LDC comes to answer this question. A q-query LDC is an error-correcting code that allows to retrieve any particular symbol of the message by reading only q symbols of the codeword.
It turns out that LDCs are directly related to representation theory and to extremal combinatorics. In this talk we are going to survey different approaches for construction of LDCs. In particular we are going to show that if there exists an irreducible representation (\rho, V) of a group  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-> F^G.

Coffee will be served at 12:00 before the lecture
at Schreiber building 006