Séminaire INFRES TELECOM ParisTech
Organisateurs:Hugues Randriam &Dario Rossi
Speaker:János Körner (Univ. Rome 1 “La Sapienza”)
Title:Structures of diversity
Abstract:In information theory,one is mostly interested in the maximum cardinality of a set of strings of a common length n with the property that any two (or more) of the strings from the set differ in some particular manner. This happens because the strings are codewords used to transmit information through a noisy device so that the output sequences are distorted versions of the inputs,yet we need to tell them apart in order to recover,at the receiving end,the information encoded by different input strings.
In the more combinatorial zero-error problems,the pairwise difference relation between code strings can be expressed in terms of a graph. The vertices of the graph are the symbols from the input alphabet of the physical channel,and adjacent vertices correspond to symbols which cannot be confused at the receiving end. In 1956 Shannon asked for the determination of the maximum number of strings of length n such that any two of them differ in some coordinate in a pair of adjacent vertices of the graph G. The exponential asymptotics of this number,as n goes to infinity,is the capacity of the graph.
From an abstract point of view,a difference relation for strings is a pairwise relation whose main feature is that of being irreflexive. A further characteristic of a difference relation is that if two strings have a projection onto a subset of their coordinates that are in this relation as strings,then already this guarantees that the pair of strings are in the same relation. We will refer to this property as local verifiability. It is easy to see how any difference relation leads to a concept of capacity.
We will give several examples of problems in extremal combinatorics that we can solve within this framework,using information theoretic intuition and methods.
TelecomParisTech-QoS-Aruna Jayasuriya (PDF)
Short bio: János Körner was born in Budapest,Hungary,on November 30,1946. He received the degree in mathematics at the Eötvös University,Budapest,Hungary,in 1970.
After graduation,he joined the Mathematical Institute of the Hungarian Academy of Sciences,Budapest,where he worked until he left Hungary,in 1989. From 1981 to 1983,he was on leave at AT&T Bell Laboratories,Murray Hill,NJ. At present,he is a Professor in the Department of Computer Science at the University of Rome 1 “La Sapienza”,Rome,Italy.
With Imre Csiszár,he is the author of the book “Information Theory:Coding Theorems for Discrete Memoryless Systems”. His main research interests are in combinatorics,information theory,and their interplay. Prof. Körner served as Associate Editor for Shannon Theory for IEEE TRANSACTIONS ON INFORMATION THEORY from 1983 to 1986.
