The last several years have witnessed major theoretical advances in communications and coding theory resulting in a new coding concept called codes on graphs. Codes on graphs, and specially their prime examples, low-density parity check (LDPC) codes and turbo codes is a research area of great current interest. One of the key results regarding codes on graphs is that iterative decoding algorithms developed for these codes are instances of probability propagation algorithms that have been independently developed in the expert systems literature. When operating on a graphical model of a code, belief propagation algorithms show an unprecedented ability to correct errors that occur due to noise and impairments encountered during the transmission/storage of information. Moreover, it is known that codes on graphs can approach optimal theoretical limits of reliable transfer of information. The theory of codes on graphs has not only improved the error performance of communications systems, but it has also opened new research avenues for investigating code constructions and alternative sub-optimal decoding schemes.
      Despite the fact that in recent years there has been a great deal of research in both code construction and decoding algorithms, codes on graphs have not yet found an application in communication systems in which very low bit error rates are required, such as fiber optics communications systems. One of the reasons (if not a main reason) is that no analytical characterization of the bit error rate (BER) performance is known for these codes under iterative decoding.
      Recently, the relationship between codes on graphs and spin models was discovered and described in a series of papers. Following this relation, it has been shown that turbo codes correspond to “coupled spin chains”, while LDPC represent “spin models on diluted graphs”. Using the spin model approach it is possible to re-derive many known results regarding conditions for error-free communication with iterative decoding, since error-thresholds correspond to phase transitions in spin models. Moreover, it seems that the theory of spin glasses can be used to determine if an iterative decoding algorithm can reach the threshold of optimum decoding in a finite number of iterations, or if there exists a lower dynamical threshold where the decoding algorithm gets trapped in a locally stable state. Answering this question would resolve issues regarding the decoding complexity of LDPC codes, BER characterization at very low error probabilities, the existence of error floor, etc.
      For emerging new coding paradigms to benefit from the achievements made in statistical physics, and for physics to benefit from recent major theoretical advances in coding theory, it is necessary to identify principles and methods unique to both disciplines despite their terminological difference. We believe that an effort to better understand and mathematically formulate them will offer new directions in information and coding theory as well as in statistical physics. It will also motivate revisiting the existing communications system models and coding and detection methodologies, which, in turn, can improve traditional systems as well.
      This workshop will bring together experts who work on coding theory and statistical physics from a variety of viewpoints. In order to facilitate a synthesis of perspectives, the workshop will be organized around half-day sessions followed by active discussions. The workshop will be an excellent venue with outstanding speakers and high-quality technical content.
      The primary topics of inquiry will be:

Invited Speakers ( all confirmed):

Alexei Ashikhmin (Bell-Labs)— aea@research.bell-labs.com
Alexander Barg (U Maryland)— abarg@ieee.org
Vladimir Chernyak (Wayne State U.) — chernyak@chem.wayne.edu
Yoshiyuki Kabashima (Tokyo Tech) — kaba@dis.titech.ac.jp
Ljupco Kocarev (UCSD)— lkocarev@ucsd.edu
Ralph Koetter (UIUC)— koetter@csl.uiuc.edu
Marc Mezard (Orsay, Paris) — mezard@lptms.u-psud.fr
Olgica Milenkovic (Boulder) — olgica.milenkovic@colorado.edu
Andrea Montanari (ENS, Paris) — montanar@lpt.ens.fr
Tom Richardson (Flarion, NJ) — richardson@flarion.com
David Saad (Aston, Birmingham) — saadd@aston.ac.uk
M. Amin Shokrollahi (EPFL, Switzerland) — amin@shokrollahi.com
Paul H. Siegel (UCSD) — psiegel@ucsd.edu
Nicolas Sourlas (ENS, Paris) — sourlas@lpt.ens.fr
Martin Wainwright (Berkeley) — wainwrig@eecs.berkeley.edu
Jonathan S. Yedidia (Mitsubishi) — yedidia@merl.com

Local Participants:

• Richard Hughes (P-21)
• Misha Stepanov (CNLS & T-13)
• Zoltan Toroczkai (CNLS & T-13)

This Workshop is Open to the Interested Public.

Administrative coordinator:
Roderick Garcia, (505) 667-1444