Journ̩e Claude Shannon Р1/07/2016

Francois Baccelli (University of Texas at Austin, INRIA) and Marc Lelarge (INRIA) in collaboration with the LINCS are happy to host a day dedicated to Claude Shannon.

Registration
Please email maura.covaci@telecom-paristech.fr to register for the day’s talks.

Arriving at the venue:
LINCS (23 avenue d’Italie, 75013).

Metro stop Place d’italie. Lines 5,6,7

Once you arrive at the information desk at the bottom of the building the hostess will direct you to the 4th floor via the elevators on the avenue d’Italie side. The talks will be held in the RENNES conference room at EIT Digital.

Program:
 

8h45-9h15 Breakfast

9h15-9h30 Welcome by LINCS and EIT Digital

9h30-10h30 Florent KRZAKALA, UPMC
Shannon Capacity and Spatially-Coupled Superposition Codes

10h30-11h: Coffee Break

11h-12h: Venkat ANANTHARAM, UC Berkeley
The Boolean Model in the Shannon Regime

12h-13h30: Lunch Break

13h30-14h30: Jean-Pierre TILLICH, INRIA
Attaining the capacity with  Reed-Solomon codes through the $(U|U+V)$
construction and Koetter-Vardy soft decoding.

14h30-15h30 Philippe JACQUET, Nokia
What Shannon would have said about Artificial Intelligence?

15h30-16h00: Coffee Break

16h00-17h00: Stéphane BOUCHERON,  Université Paris-Diderot, ENS-Ulm
(Almost) adaptive coding against finite alphabets. Regularly varying
envelopes.

Florent KRZAKALA, UPMC

Shannon Capacity and Spatially-Coupled Superposition Codes

Abstract: Since Shannon’s celebrated 1968 article, the quest for a capacity achieving error correction scheme has guided a large part of coding theory. Recently, it has been shown that a new strategy, Spatially-Coupled Superposition Coding, is capacity acheiving on any memory-less channel while admitting a polynomial iterative decoding. We shall describe this approach, and underline the analogies and difference with low density parity check codes and compressed sensing.

Venkat ANANTHARAM, UC Berkeley

The Boolean Model in the Shannon Regime

Abstract: This talk will survey recent results on Boolean stochastic geometry in high dimensional Euclidean spaces. A Boolean model in $\R^n$ consists of a homogeneous Poisson point process in $\R^n$ and of independent and identically distributed random closed sets of $\R^n$ centered on each atom of this point process.The Shannon regime features a family of Boolean models indexed by $n \ge 1$, where the $n$-th model has a Poisson point process of intensity $e^{n \rho}$ and random compact sets with diameter of order $\sqrt{n}$, and lets $n$ tend to $\infty$. A typical example is that where each random compact set is an $n$ ball of radius  distributed like $\bar X_n \sqrt{n}$, with $\bar X_n$ satisfying a large deviations principle.

The main focus of the talk will be on the asymptotic behavior of classical Boolean stochastic geometry quantities, like volume fraction, percolation threshold or mean cluster size, in this Shannon regime. The analysis of this asymptotic regime is motivated by problems in information theory, and leads to new results on error exponents, which describe the rate of decay to 0 of the probability of decoding error in channel coding.

Jean-Pierre TILLICH, INRIA

Attaining the capacity with  Reed-Solomon codes through the $(U|U+V)$ construction and Koetter-Vardy soft decoding (joint work with Irene Màrquez-Corbella)

Abstract : In this talk, we show how to attain the capacity of discrete symmetric channels by considering iterated $(U|U+V)$ constructions with Reed-Solomon code components. These Reed-Solomon codes are decoded with the Koetter-Vardy soft decoder and we show that when the number of levels of the iterated $(U|U+V)$ construction tends to infinity, we attain the capacity of any discrete symmetric channel in this way. This result follows from the polarization theorem together with a simple lemma explaining how the Koetter-Vardy decoder behaves for Reed-Solomon codes of rate close to $1$. However, even if this way of attaining the capacity of a symmetric channel is essentially the polarization theorem, there are some differences with standard polar codes. Indeed, with this strategy we can operate successfully close to channel capacity even with a small number of levels of the iterated $(U|U+V)$ construction and the probability of error decays exponentially with the code length in such a case. Moreover, when comparing this strategy to Reed-Solomon codes decoded with the Koetter-Vardy decoding algorithm, it does not only improve the noise level that the code can tolerate, it also results in a significant complexity gain.

Philippe JACQUET, Nokia Bell Labs

What Shannon would have said about Artificial Intelligence?

Abstract: We know that Turing and Shannon met in Washington in 1943, during the war. We don’t know what they precisely discussed about, but it was very likely around confidential secure telephone communication setting. They probably also discussed about chess and machine solving chess puzzles. But what would have been their discussion about the fundamental limit of artificial intelligence with regards to information theory. Can really an artificial intelligence be able evolve so fast that it will supersede human intelligence (Stephen Hawking concern)? Beyond the Turing test, but without needing to reach the limit of computability established by Turing, we are going to discuss what Information Theory could answer to this question.

Abstract : We study the problem of lossless universal source coding for stationary memoryless sources on countably infinite alphabets. This task is generally not achievable without restricting the class of sources over which universality is desired. We propose natural families of sources characterized by a common dominating envelope. We particularly emphasize the notion of adaptivity, which is the ability to perform as well as an oracle knowing the envelope, without actually knowing it. This is closely related to the notion of hierarchical universal source coding, but with the important difference that families of envelope classes are not discretely indexed and not necessarily nested.  We attempt and partially succeed in characterizing the classes of envelopes over which adaptive universal source coding is possible, namely by including (very) light-tailed ad max-stable (heavy-tailed) envelopes which are excellent models in many applications, such as natural language modeling. We derive a minimax lower bound on the redundancy of any code on such envelope classes, including an oracle that knows the envelope. We then propose constructive codes that do not use knowledge of the envelope. Codes are computationally efficient and combine mixture coding for common symbols or small symbols, or for the pattern generated by the message, and censoring for rare symbols. Our technical results are founded on methods from regular variation theory and concentration of measure.

Travail avec commun avec Anna Ben-Hamou Dominique Bontemps, Elisabeth Gassiat, Mesrob I. Ohannessian
Références : arXiv:1402.6305, arXiv:1412.8652,  arXiv:1202.0258, WIP