A proof of the RM code capacity conjecture

Abstract:
In 1948, Shannon used a probabilistic argument to prove the existence of codes achieving channel capacity. In 1954, Muller and Reed introduced a simple deterministic code construction, conjectured shortly after to achieve channel capacity. Major progress was made towards establishing this conjecture over the last decades, with various branches of discrete mathematics involved. In particular, the special case of the erasure channel was settled in 2015 by Kudekar at al., relying on Bourgain-Kalai’s sharp threshold theorem for symmetric monotone properties. The case of error channels remained however unsettled, due in particular to the property being non-monotone and the absence of techniques to obtain fast local error decay (despite Reeves-Pfister’s result on a vanishing local error). In this talk, we provide a proof of the general conjecture. The proof circumvents the use of Bourgain-Kalai’s theorem by establishing first a “weak threshold” property that relies solely on symmetries. The proof then proceeds with a new boosting framework for coding, improving the weak local error to a strong global error by relying on sunflower structures (as in Erdős-Rado 1960). Joint work with Colin Sandon.

Bio:
Emmanuel Abbé received his Ph.D. degree from the EECS Department at the Massachusetts Institute of Technology (MIT) in 2008, and his M.S. degree from the Department of Mathematics at the Ecole Polytechnique Fédérale de Lausanne in 2003. He joined EPFL in 2018 as a Full Professor, jointly in the Mathematics Institute and the School of Computer and Communication Sciences, where he holds the Chair of Mathematical Data Science. He is the recipient of the Foundation Latsis International Prize, the Bell Labs Prize, the NSF CAREER Award, the Google Faculty Research Award, the Walter Curtis Johnson Prize, the von Neumann Fellowship from the Institute for Advanced Study, the IEEE Information Theory Society Paper Award, and a co-recipient of the Simons-NSF Mathematics of Deep Learning Collaborative Research Award.