METRIC 2011 Trimester at Institut Henri Poincaré (Paris, France)
Workshop on Expanders and derandomization (March 21-25, 2011)
Mar 23, 15:00-16:00 - Alex Lubotzky (Hebrew U., Jerusalem)
Ramanujan graphs and error correcting codes
----
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
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.
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.
Joint work with Tali Kaufman.
Workshop on Expanders and derandomization (March 21-25, 2011)
Mar 23, 15:00-16:00 - Alex Lubotzky (Hebrew U., Jerusalem)
Ramanujan graphs and error correcting codes
----
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
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.
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.
Joint work with Tali Kaufman.
Category
🤖
Technologie