DIMACS Workshop on Codes and Complexity

December 4-7, 2001
DIMACS Center, CoRE Bldg., Room 431, Rutgers University, Piscataway, NJ

Amin Shokrollahi, Digital Fountain, amin@digitalfountain.com
Daniel Spielman, MIT, spielman@math.mit.edu
Ruediger Urbanke, Ecole Polytechnique Federale de Lausanne (EPFL), rudiger.urbanke@epfl.ch
Presented under the auspices of the:
Special Focus on Computational Information Theory and Coding and the
Special Focus on Mathematics and the Foundations of Computer and Information Science.

Ever since Shannon's seminal paper on information theory more than 50 years ago, the construction of codes which have efficient encoders and decoders with performance arbitrarily close to Shannon's bound has been the supreme goal of coding research. The last few years have witnessed tremendous progress towards achieving this goal. One of the most intriguing aspects of recent developments has been a cross fertilization of ideas in coding and information theory, theoretical computer science, and physics. Especially the connection to theoretical computer science ultimately led to an asymptotic analysis of many classes of codes based on graphs; conversely, coding theory has turned out to be an indispensable tool in many recent exciting developments in theoretical computer science, such as the design of probabilistically checkable proofs, or pseudo random generators.

The goal of this workshop is to bring together researchers in coding and information theory, theoretical computer science, and physics in the hope of further stimulating cross-collaboration. The workshop will be preceded by a tutorial on low-density parity-check codes intended to bring graduate students and other interested researchers with little or no previous background up to speed in this important area of research. There will be several invited 45 minute talks on various topics that elucidate connections of coding theory to the above mentioned areas. There will also be a number of contributed talks.

Next: Call for Participation
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on August 28, 2001.