Maël Le Treust - Communication systems
Date: - Location: Eurecom
Abstract : Zero-error coding encompasses a variety of source and channel problems where the probability of error must be exactly zero. This condition is stricter than that of the vanishing error regime, where the error probability goes to zero as the code blocklength goes to infinity. In general, zero-error coding is an open combinatorial question. We investigate two unsolved zero-error problems: the source coding problem with side information and the channel coding problem. We focus our attention on families of independent problems for which the distribution decomposes into a product of distributions, corresponding to solved zero-error problems. A crucial step is the linearization property of the optimal rate which does not always hold in the zero-error regime, unlike in the vanishing error regime. We derive a condition under which the linearization properties of the complementary graph entropy H for the AND product of graph and for the disjoint union of graphs are equivalent. Then we establish the connection with a recent result obtained by Wigderson and Zuiddam and by Schrijver, for the zero-error capacity C0. As a consequence, we provide new single-letter characterizations of H and C0, for example when the graph is a product of perfect graphs, which is not perfect in general, and for the class of graphs obtained by the product of a perfect graph G with the pentagon graph C5. By building on Haemers result for C0, we also show that the linearization of H does not hold for the product of the Schläfli graph with its complementary graph. Biography : Maël Le Treust is CNRS researcher since Oct. 2013, working at IRISA UMR 6074 in Rennes, France. From Oct. 2013 to Aug. 2022, he was researcher at ETIS laboratory UMR 8051, CY Cergy Paris Université, ENSEA, CNRS. He received the M.Sc. degree in Optimization, Game Theory and Economics (OJME) from the Université de Paris VI in 2008 and the Ph.D. degree in Information Theory from the Université de Paris Sud XI, L2S UMR 8506 Gif-sur-Yvette, in 2011. In 2012-2013, he was a post-doctoral researcher at LIGM UMR 8049 in Marne-la-Vallée, France, and at Université INRS and McGill University in Montréal, Canada. His research interests include Information Theory, Game Theory, Optimization, Economics and Communications. From 2019 to 2023, he serves as secretary of the Scientific Council of CNRS Informatics. Since Oct. 2021, he serves as an Associate Editor for IEEE Transactions on Information Theory.
