Computer Science/Discrete Mathematics Seminar II

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 code word. 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, \dotsc, 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 \to 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.