[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

*REMINDER*

THEORY SEMINAR

Tuesday, April 9, 2013
3:00 p.m.
Ryerson 251
 
Klim Efremenko
Tel-Aviv University
www.cs.tau.ac.il/~klim/
 
Title:  From Irreducible Representations to Locally Decodable Codes
 
Abstract: 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.
 
In this talk we present a new approach for the  construction of  LDCs from the 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.
 
Host: Prof. Alexander Razborov
 
*Refreshments will be served prior to the talk at 2:30 in Ryerson 255*
 
 
 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20130409/9acbe618/attachment.htm