ZiF Logo

General Theory of Information Transfer

Opening Conference

November 4 - 9, 2002

Abstracts

Conference program (PDF-file, 31 kB)

At the beginning of the opening conference, the Managing Director of the ZiF, Prof. Dr. Ipke Wachsmuth, welcomed over 70 researchers from 19 different countries.

Reception in Bielefeld's old city hall

A picture taken at mayor Helling's reception in honor of the Research Group in the old town hall of Bielefeld.

From left to right:
Prof. Vladimir Levenshtein (Moscow)
Prof. Rudolf Ahlswede (Research Group organizer)
Dr. Anastassia Vasil'eva (Novosibirsk)
Prof. Ipke Wachsmuth (Managing Director of the ZiF)

Rudolf Ahlswede then outlined the leading ideas of the research program. After giving a compact description of Shannon's celebrated theory of communication he described his creation of the theory of identification in the presence of noise, which was worked out together with Guenter Dueck. It goes considerably beyond Shannon's theory. "Transmission" (classical) concerns the question "How many messages can we transmit over a noisy channel?" One tries to give an answer to the question "What is the actual message from M={1,...,m}?"
On the other hand in "identification" it is asked "How many possible messages can the receiver of a noisy channel identify?" One tries to give an answer to the question "Is the actual message i ?" Here i can be any member of the set of possible messages N={1,2,...,n}.
This theory initiated other research areas on Alarm Systems and Common Randomness, which gave a new impetus to Cryptology. It also led to the discovery of new methods which became fruitful even for the classical theory of transmission, for instance in studies of robustness like arbitrarily varying channels, optimal coding procedures in case of complete feedback, novel approximation problems for output statistics and generation of common randomness, the key issue in Cryptology.
Moreover the work on identification has led to reconsiderations of the basic assumptions of Shannon's theory. It deals with "messages", which are elements of a "prescribed set of objects", known to the communicators. The receiver wants to know the true message. This basic model occurring in all engineering work on communication channels and networks addresses a very special communication situation. More generally they are characterized by
1. The questions of the receivers concerning the given "ensemble", to be answered by the sender(s)
2. The prior knowledge of the receivers
3. The senders' prior knowledge.
It seems that the whole body of present day Information Theory will undergo serious revisions and some dramatic expansions. A general theory of information transfer abbreviated as GTIT, was developed and to some degree analyzed. It extends the frontiers of information theory in several directions.
Another direction of research was initiated by the work of Ahlswede, Cai, Li and Yeung in which first optimal results on information flows in networks were presented. Prior to their work it was not recognized that information flows follow completely different rules as flows of physical commodities.
Other researchers suggested further information problems from fields like, for instance, Bioinformatics, Animal Communication and Quantum Theory.
The main goal of the research project is to explore how the new theory of general information transfer can find applications in other fields both along theoretical and experimental lines. Furthermore it needs to be examined whether the informational phenomena from other areas make it necessary to extend existing or even create new models.
In the present shape of the research group the main directions of research will be in the following fields: Biology - Animal Communication and Language Evolution, Cryptology, General Theory of Information Transfer, Networks - Flows and Learning, Philosophy - Concepts of Information, Quantum Information, Reconstruction of Sequences, Statistics and Probability Theory, Search, Sorting and Ordering.
It should be noted that there are further areas with interesting independent information problems, like Chemistry or Game Theory, but this would go beyond the scope of the already very comprehensive project.
After formulations of mathematical models in the above mentioned areas have been obtained it is to be expected that difficult combinatorial problems arise, which will then be attacked by experts in mathematics.
After the two preparatory meetings in the beginning of 2002, the opening conference also helped attracting further outstanding scientists to join the project as fellows.
Two days of the conference were devoted to the memory of Levon Khachatrian from the Department of Mathematics of the University of Bielefeld. There were talks about each field of research to which he contributed significantly. This included the fields: Combinatorial Number Theory, Cryptography, Combinatorics, Coding Theory and Networks. One lecture had the title "Extremely Strong Results of Levon Khachatrian in Extremal Set Theory".

Titles

Rudolf Ahlswede: General Theory of Information Transfer and Combinatorics
Klaus Mainzer: Information Dynamics in Nature and Society
Alberto Apostolico: Bearable Monotonies of Surprise
Laxmi Parida: Using Permutation Patterns in Bioinformatics
Raimund Apfelbach: Chemical Information Transfer in Phodopus Hamsters
Zhanna Reznikova: Applying Ideas of Information Theory to Study Animal Communicative and Cognitive Skills
Lloyd Demetrius: Quantum Statistics and Allometric Scaling Relations in Biology
Elena V. Konstantinova: Information Indices and Their Discriminating Power
Stefano Galatolo: Information in Weakly Chaotic Dynamical Systems
Ludwig Staiger: Information, Entropy and Dimension
Imre Csiszar: Secret Key Capacities for Multiple Terminals
Mariam and Evgueni Haroutunian: E-Capacities of Varying Channels
Sándor Csibi and Edward van der Meulen: Huge-Size Codes for Identification via a Multiple Access Channel Under a Word Length Constraint
Yuri Shtarkov: Joint Matrix Universal Codes of Sequences of Independent Symbols
Peter Harremoës: Testing Binomial vs. Poisson Distributions Using Information Theoretic Methods
Vladimir Blinovsky: Large Deviations in the Commutative and Non-Commutative Case
Viacheslav Prelov and Edward van der Meulen: Optimal Covering of Ellipsoids With Balls in the Hamming Space
Sergey Avgustinovich and Anastassia Yu. Vasillieva: Testing Sets for 1-Perfect Codes
Dmitrii Nogin: Bounds on Packings of Spheres in the Grassmann Manifold
Vladimir Balakirsky: Estimates of the Bit Error Probabilities for Linear Block Codes and Symmetric Binary-Input Memoryless Channels
Gergely Berczi: On Finite Pseudorandom Sequences of k Symbols
In Memory of Levon Khachatrian
Gurgen Khachatrian: Remembering Levon
Sergej Adian: Investigation of Periodical Groups Using Combinatorial Methods
Victor Zinoviev: On Goethals Codes and Kloosterman Sums Over GF(2m)
András Sárközy: On Primitive Sequences
Gyula Katona: Extremely Strong Results of Levon Khachatrian in Extremal Set Theory
Luisa Gargano: Broadcasting in Communication Networks
Session on Combinatorial Number Theory and Cryptography
Gregory Freiman and Aleksandr Yudin: On the Interface Between Probability Theory (Limit Theorems) and Additive Number Theory (Structure Theory of Set Addition)
Melvyn Nathanson: Additive Number Theory and the Ring of Quantum Integers
Gyula Karolyi: Transversals of Additive Latin Squares
Jean-Louis Nicolas: Sets of Parts Such That the Partition Function is Even
Oriol Serra: The Erdös-Turan Property for a Class of Additive Basis
Christian Mauduit: Measures of Pseudorandomness for Finite Sequences
James Massey: Reed Muller Codes and Certain Stream Ciphers
Session on Combinatorics
Ian Roberts: Completely Separating Systems
Harout Aydinian: Intersection Theorems Under Dimensions Constraints: The Unrestricted Case
Peter L. Erdös: Property B and Some Generalization
Norihide Tokushige: Some Results on Multiply Intersecting Families
Konrad Engel: Optimal Multileaf Collimator Field Segmentation for Inverse Radiotherapy Planning
Christian Bey: Remarks on an Edge Isoperimetric Problem
Session on Coding and Networks
Vladimir Levenshtein: Combinatorial Problems Motivated by Comma Free Codes
Grigori Kabatiansky: Hash Codes and Functions: Bounds and Constructions
Melsik Kyureghyan: Recurrent Methods for Constructing Sequences of N-Polynomials Over F2s
Faina Solov'eva: Steiner Triple Systems Bi-Embedded in Nonorientable Surfaces
Stefan Dodunekov: Proper Codes: an Overview and Recent Results
Jana Dittmann: Invertible Watermarking Combined With Electronic Signatures for Image and Audio Authentication
Boris Ryabko: A new Statistical Testing for Random Numbers and its Application to Some Cryptographic Problems
Kingo Kobayashi: Percolation on k-ary Trees
Rüdiger Reischuk: Online Algorithms - The Power of Knowledge When Accessing Data
Maciej Liskiewicz: Private Computations in Incomplete Networks
Vladimir Batagelj: Efficient Algorithms for Citation Network Analysis
Ingo Wegener: On the Complexity of Black-Box Search
Christian Deppe: An Upper Bound for the Binary Channel With Feedback and a Fixed Number of Errors
Marina Kyreghyan: Complexity of Monotonicity Checking
Gohar Kyreghyan: Minimal Polynomials of the Modified De Bruijn Sequences
Timothy Havel: Information Dynamics in Open Quantum Systems
Rusins Freivalds: On Quantum Finite Automata
Hiroshi Nagaoka: Hypothesis Testing, Channel Coding and Information Spectrum in Quantum Information Theory
Rainer Wilmink: On Quantum Broadcast Channels
Armin Uhlmann: Quantum Information Transfer from one System to Another one
Erdal Arikan: An Information Theoretic Analysis of Grover's Algorithm
Jens Eisert: From Reversibility to Irreversibility and Back Again: Asymptotic State Manipulation in Quantum Mechanics

Participants

Sergej I. Adian (Moskau), Rudolf Ahlswede (Bielefeld), Raimund Apfelbach (Tübingen), Alberto Apostolico (Padua), Erdal Arikan (Ankara), Suren Arzumanyan (Bielefeld), Sergey Avgustinovich (Novosibirsk), Nihat Ay (Leipzig), Harout Aydinian (Bielefeld), Lars Bäumer (Bielefeld), Vladimir Balakirsky (St. Petersburg), Vladimir Batagelj (Laibach), Gergely Berczi (Budapest), Christian Bey (Rostock), Vladimir Blinovsky (Moskau), Ning Cai (Bielefeld), Sándor Csibi (Budapest), Imre Csiszar (Budapest), Lloyd Demetrius (Cambridge, MA), Christian Deppe (Bielefeld), Jana Dittmann (Dessau), Stefan Dodunekov (Sofia), Arkadii G. Dyachkov (Moskau), Jens Eisert (London), Konrad Engel (Rostock), Peter L. Erdös (Budapest), Gregory Freiman (Tel Aviv), Rusins Freivalds (Riga), Zoltan Furedi (Budapest), Stefano Galatolo (Pisa), Luisa Gargano (Baronissi), Evgueni Haroutunian (Jerevan), Mariam Haroutunian (Jerevan), Peter Harremoës (Kopenhagen), Timothy F. Havel (Cambridge, MA), Helmut Jürgensen (Potsdam), Gregory Kabatiansky (Moskau), Gyula Karolyi (Budapest), Gyula Katona (Budapest), Gurgen Khachatrian (Camarillo, CA), Kingo Kobayashi (Tokio), Elena Konstantinova (Novosibirsk), Gohar Kyureghyan (Magdeburg), Marina Kyureghyan (Bielefeld), Melsik Kyureghyan (Jerevan), Vladimir Levenshtein (Moskau), Maciej Liskiewicz (Lübeck), Klaus Mainzer (Augsburg), Haik Marshurian (Bielefeld), James Massey (Kopenhagen), Christian Mauduit (Marseille), Giulia Menconi (Pisa), Hiroshi Nagaoka (Tokio), Melvyn Nathanson (Bronx, NY), Jean-Louis Nicolas (Villeurbanne), Dmitrii Nogin (Moskau), Laxmi Parida (Yorktown Heights, NY), Viacheslav Prelov (Moskau), Rüdiger Reischuk (Lübeck), Zhana I. Reznikova (Novosibirsk), Ian Roberts (Brinkin, N.T.), Boris Ryabko (Novosibirsk), András Sárközy (Budapest), Oriol Serra (Barcelona), Yuri Shtarkov (Moskau), Faina I. Solov'eva (Novosibirsk), Ludwig Staiger (Halle an der Saale), Ulrich Tamm (Chemnitz), Norihide Tokushige (Okinava), Armin Uhlmann (Leipzig), Edward C. van der Meulen (Leuven), Anastassia Vasillieva (Novosibirsk), Ingo Wegener (Dortmund), Frans Willems (Eindhoven), Rainer Wilmink (Bielefeld), Aleksandr Yudin (Vladimir), Victor Zinoviev (Moskau)