Ramanujan Graphs and Error Correcting Codes
When/Where:
March 12, 2019, 3:00– 3:50 pm at the 3rd floor Atrium.
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. The construction is based on the Sipser-Spielman codes using 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. We will discuss the potential of these complexes to yield more applications to coding theory. All notions will be explained.
Joint work with Tali Kaufman.