Combinatorics Seminar

When: Sunday, June 3, 10am Where: Schreiber 309 Speaker: Alex Lubotzky, Hebrew University Title: Arithmetic groups, Ramanujan graphs and error correcting codes

Abstract:

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 expectation), 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.