FIM Lectures
FIM Lectures are single, one-hour lectures given by renowned mathematicians. They are designed as a platform for the speaker to present his or her latest results, and they are usually followed by an apéro that offers room for further in-depth discussions.
Upcoming FIM Lectures
Friday, 17 May, 16:15, HG E 7
Emmanuel Abbé (EPFL)
On the conjecture of achieving Shannon capacity with Reed-Muller codes
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 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 conjecture, introducing a new framework for establishing thresholds via boosting on flower set systems. Joint work with Colin Sandon.
The lecture is followed by an apéro.