DIMACS, the Center for Discrete Mathematics and Theoretical Computer Science, will hold a Special Focus on Computational Information Theory and Coding beginning in January 2001 and going June 2005.
The main purpose of coding theory is the reliable transmission or storage of data. It is common to think about information theory as a science concerned with theoretical limits on rates at which reliable transmission or storage of data is possible. During the course of the 50-year life of information theory, these limits (known as channel capacities) have been computed for various important telecommunications channels based on their underlying physics, which was considered given. Computational Information Theory is concerned with techniques (such as channel coding) for achieving channel capacities. Computational information theory has achieved dramatic scientific breakthroughs in recent years, and codes that come close to theoretical limits have been discovered.
This special focus will explore interconnections among coding theory, theoretical computer science, information theory, and related areas of computer science and mathematics, in order to address some of the challenges for the next 50 years - in particular wireless communication, magnetic/optical storage, the role of signal processing in networks, network information theory, and the creation of quantum information theory.
THEMES/MOTIVATION
Today, the development of coding and information theory is closely related to the explosion of information technology, with applications to the Internet and the next generation of networks technologies. The rapid development of a myriad of networked devices for computing and telecommunications presents challenging and exciting new issues for coding and information theory.
In 1948 Shannon developed fundamental limits on the efficiency of communication over noisy channels. The coding theorem asserts that there are block codes with code rates arbitrarily close to channel capacity and probabilities of error arbitrarily close to zero. Fifty years later codes for the Gaussian channel have been discovered that come close to these fundamental limits. Today, theoretical limits on rates at which reliable transmission or storage of data is possible are known for many telecommunications challenges. The same types of challenges face us in today's and tomorrow's new eras of networked, distributed computing and communications.
Coding theory has long used deep mathematical methods. We will explore the use of such mathematical ideas from linear systems theory, automata theory, algebraic geometry, etc. in the understanding of issues at the interface among coding theory, information theory, and theoretical computer science.
There are many connections between coding theory and theoretical computer science. We will explore the connections between coding theory and: upper bounds on the number of random bits used by probabilistic algorithms and the communication complexity of cryptographic protocols; lower bounds on the complexity of approximating numerous combinatorial optimization functions; characterizations of traditional complexity classes such as NP and PSPACE; and the emerging theory of program testing.
Connections between information theory/coding and other parts of science, in particular physics, go back to the need to understand the relations between Shannon's perspective on entropy and the laws of thermodynamics. Today, attention has turned to quantum mechanics and the processing of intact quantum information states, and we will explore such connections.
Coding theory is essential in numerous applied areas such as deep space communication, the theory of wireless channels, and optical/magnetic recording. Such applied areas are posing new and challenging problems for coding theorists and will be a central focus of this special focus.
The development of the ``next generation'' of networks technologies leads to many new challenges for coding and information theory. Thinking of the network as a channel should help us to understand these challenges.
The time is right to explore in depth the interface among coding theory, theoretical computer science, information theory, and parts of theoretical mathematics. The new and exciting applied problems arising from new information technologies are calling for interdisciplinary approaches. And the theoretical problems have already shown themselves to be ripe for cross-fertilization among techniques and methods.
Opportunities to Participate: The Special Focus will include:
Index of Special Focus on Computational Information Theory and Coding
DIMACS Homepage