Computer Science/Discrete Mathematics Seminar I

Locally Decodable Codes (LDCs) are a special type of error correcting codes which are constructed from finite point sets that support many small linear dependencies (e.g. many collinear triples). Despite their importance, there are still huge gaps between the known LDC constructions and lower bounds. In 2008 , Efremenko showed a framework for constructing LDCs from representations of finite groups. We strengthen Efremenko's reduction and use this strengthening, together with known bounds on LDCs, to derive new results on representations. In particular we show that if rho is an n-dimensional irreducible representation of G and rho(g) is not the identity, then it must be n/log|G| far from the identity in rank metric (this bound is the best possible in general).