http://www.dagstuhl.de/13351

August 25 – 30 , 2013, Dagstuhl Seminar 13351

Coding Theory

Organizers

Hans-Andrea Loeliger (ETH – Zürich, CH)
Emina Soljanin (Bell Labs – Murray Hill, US)
Judy L. Walker (University of Nebraska – Lincoln, US)

For support, please contact

Dagstuhl Service Team

Documents

Dagstuhl Report, Volume 3, Issue 8 Dagstuhl Report
Aims & Scope
List of Participants
Shared Documents
Dagstuhl Seminar Schedule [pdf]

Summary

While coding theory has evolved into an essential ingredient of contemporary information technology, it remains a fascinating area of research where many fundamental ideas of information theory and mathematics meet. Indeed, the diversity and profundity of recent new ideas in, and new applications of, coding theory is impressive. The following themes were of primary interest at the seminar:

Codes on graphs include turbo codes, low-density parity check codes, and a variety of similar codes. Due to the recent new idea of ``spatial coupling'', such codes can now be designed to achieve the Shannon capacity of most communication channels with practical encoders and decoders. Such codes are a perfect nurturing ground for cross-fertilization of ideas between computer science, electrical engineering, and mathematics. The mathematical tools in this area include ideas from graph theory, probability, algebra, discrete mathematics, and statistical physics.

Algebraic coding theory continues to be of supreme theoretical and practical interest. Prime examples of this area are Reed-Solomon codes, codes from algebraic geometry, and codes obtained from algebraically constructed graphs. Recent advances in the field include, in particular, list-decoding algorithms for various classes of algebraic codes. Emerging relationships between this area and codes on graphs appear to be promising for future research.

Polar codes (discovered by Arikan in 2008) are a breakthrough of utmost significance. Such codes are provably capacity-achieving on very many channels with very low-complexity (and very practical) encoders and decoders. These codes rely on a new large-system limit that combines information theory and coding theory more smoothly than any prior coding technique. The investigation of such codes, including their combination with other coding techniques (such as codes on graphs and algebraic codes), is an exciting new area of research.

Network coding aims at improving data transmission (throughput, reliability, latency, etc.) in networks. This area is still quite young, but it has begun to influence the design of methods and protocols of content delivery in the internet. There is a diverse set of network coding problem formulations, and network coding can be (and has been) studied within a number of different theoretical frameworks, such as algebraic, combinatorial, information theoretic, and linear programming frameworks.

Codes for cloud applications are about distributed storage of large amonts of data. Diverse requirements on reliability, access latency, updatability, and repairability pose entirely new challenges for coding theory.

In addition, there were also two talks on topics in coding theory inspired by biology.

The seminar brought together 45 high-caliber researchers with backgrounds and interests in these different areas. The seminar was held in the usual Dagstuhl style, with a rather light program of formal presentations and much room for informal interaction. It was interesting and stimulating to hear of developments outside one's own speciality, and (to the best of our knowledge) all attendants greatly enjoyed the seminar.

License
  Creative Commons BY 3.0 Unported license
  Hans-Andrea Loeliger, Emina Soljanin, and Judy L. Walker

Dagstuhl Seminar Series

Classification

  • Algorithms And Complexity
  • Networks
  • Cryptography
  • Algebraic Techniques

Keywords

  • Algebraic coding theory
  • Complexity theory
  • Cryptography
  • Graph theory
  • Graph based codes
  • Information theory
  • Randomized algorithms
  • Networking
  • Data distribution

Book exhibition

Books from the participants of the current Seminar 

Book exhibition in the library, ground floor, during the seminar week.

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.

NSF young researcher support