On the conjecture of achieving Shannon capacity with Reed-Muller codes
Event details
Date | 14.05.2024 |
Hour | 11:15 › 12:15 |
Speaker | Prof. Emmanuel Abbe - EPFL SB/IC |
Location | |
Category | Conferences - Seminars |
Event Language | English |
In 1948, Shannon used a probabilistic argument to show the existence of codes achieving a maximal rate defined by the channel capacity. In 1954, Muller and Reed introduced a simple deterministic code construction, based on polynomials evaluations, conjectured shortly after to achieve Shannon capacity. Major progress was made towards establishing this conjecture over the last decades. In particular, the special case of the erasure channel was settled by Kudekar at al. using the sharp threshold theorem for monotone symmetirc properties by Bourgain-Kalai, and for more general error channels, vanishing error bounds were obtained for the global error at vanishing code rate by Abbe-Shpilka-Wigderson and for the local error at constant code rate by Reeves-Pfister. The general conjecture had remained however unsettled, due in particular to the absence of sharp threshold results for non-monotone properties. This talk presents a proof of the general conjecture, introducing a new framework for establishing thresholds via boosting on flower set systems. Joint work with Colin Sandon.
Practical information
- Informed public
- Free
Organizer
- IPG Seminar
Contact
- olivier.levê[email protected]