[METRIC 2001] Alex Lubotzky - Workshop on Expanders and Derandomization at Institut Henri Poincaré (2011)

METRIC 2011 Trimester at Institut Henri Poincaré (Paris, France)<br />Workshop on Expanders and derandomization (March 21-25, 2011)<br />Mar 23, 15:00-16:00 - Alex Lubotzky (Hebrew U., Jerusalem)<br />Ramanujan graphs and error correcting codes<br />----<br />A long standing conjecture (with a number of partial results) asserts that there are no good cyclic codes. For example there are no such LDPC<br />codes. Kaufman and Wigderson showed that this is also the case when the acting cyclic group is replaced by a solvable group and asked about the general case.<br />We saw that in contrary to those results, there exist highly symmetric LDPC good codes. Our explicit construction is based on the Ramanujan graphs constructed by Lubotzky-Samuels-Vishne (as special cases of Ramanujan complexes) which are shown to be edge transitive.<br /><br />Joint work with Tali Kaufman.