Uploaded April 2026 | Updated September 2026, 3 weeks ago
Computer Science/Discrete Mathematics Seminar I
11:00am|Simonyi Hall 101 and Remote Access
Topic: Locally Decodable Codes and Representations of Finite Groups
Speaker: Zeev Dvir
Affiliation: Princeton University
Date: April 27, 2026
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).
Computer Science/Discrete Mathematics Seminar I
11:00am|Simonyi Hall 101 and Remote Access
Topic: Locally Decodable Codes and Representations of Finite Groups
Speaker: Zeev Dvir
Affiliation: Princeton University
Date: April 27, 2026
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).
