Mathematics Colloquium

---

Ramanujan Graphs and Symmetric Error Correcting Codes

Speaker: Alex Lubotzky, Hebrew University of Jerusalem

Location: Warren Weaver Hall 1302

Date: Monday, September 29, 2014, 3:45 p.m.

Synopsis:

While many of the classical codes are cyclic, a long standing conjecture asserts that there are no `good' cyclic codes. In recent years, interest in symmetric codes has been stimulated by Kaufman, Sudan, Wigderson and others (where symmetric means that the acting group can be any group). Answering their main question (and contrary to common expectations), we show that there DO exist symmetric good codes. In fact, our codes satisfy all the "golden standards" of coding theory. Our construction is based on the Ramanujan graphs constructed by Lubotzky-Samuels-Vishne as a special case of Ramanujan complexes. The crucial point is that these graphs are edge transitive and not just vertex transitive as in previous constructions of Ramanujan graphs. These complexes are obtained as quotients of the Bruhat-Tits building modulo the action of suitable arithmetic groups. We will discuss the potential of these complexes and their cohomology to yield more applications to coding theory. All notions will be explained.

Joint work with Tali Kaufman.