Dagstuhl Seminar 13351
Coding Theory
( Aug 25 – Aug 30, 2013 )
Permalink
Organizers
- Hans-Andrea Loeliger (ETH - Zürich, CH)
- Emina Soljanin (Bell Labs - Murray Hill, US)
- Judy L. Walker (University of Nebraska - Lincoln, US)
Contact
Schedule
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 seminar intends to bring together researchers in key areas of coding theory with diverse backgrounds and interests. The following areas will be at the center of the seminar.
Codes on graphs.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. 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 expander 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. The discovery of polar codes by Arikan (2008) was 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, and their combination with other coding techniques (such as codes on graphs and algebraic codes) is an exciting new area of research.
Network coding. 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 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. A key issue of cloud services is how to efficiently maintain reliable dis- tributed storage. When data is stored in a distributed manner, both the efficient recovery of damaged data and the updating of partially obsolete data pose entirely new challenges for coding theory.
Theoretical computer science. In recent years, theoretical computer science has contributed new ideas to coding theory (e.g., for codes on graphs) and vice versa. Nonetheless, we feel that several good ideas in computer science have so far been neglected in coding theory, and vice versa. It is hoped that the seminar will bring people with complementary backgrounds together.
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.
- Daniel Augot (Ecole Polytechnique - Palaiseau, FR) [dblp]
- Angela Barbero (University of Valladolid, ES) [dblp]
- Alexander Barg (University of Maryland - College Park, US) [dblp]
- Eimear Byrne (University College Dublin, IE) [dblp]
- Pascale Charpin (INRIA - Le Chesnay, FR) [dblp]
- Gerard Cohen (ENST - Paris, FR) [dblp]
- Stark C. Draper (University of Toronto, CA) [dblp]
- Iwan M. Duursma (University of Illinois - Urbana Champaign, US) [dblp]
- Salim El Rouayheb (Illinois Institute of Technology, US) [dblp]
- Marcelo Firer (State University of Campinas - Brazil, BR) [dblp]
- Heide Gluesing-Luerssen (University of Kentucky, US) [dblp]
- Elisa Gorla (Université de Neuchâtel, CH) [dblp]
- Marcus Greferath (University College Dublin, IE) [dblp]
- Hamed S. Hassani (EPFL - Lausanne, CH) [dblp]
- Michael Heindlmaier (TU München, DE) [dblp]
- Tor Helleseth (University of Bergen, NO) [dblp]
- Werner Henkel (Jacobs Universität - Bremen, DE) [dblp]
- Tracey Ho (CalTech - Pasadena, US) [dblp]
- Tom Hoholdt (Technical University of Denmark - Lyngby, DK) [dblp]
- Anna-Lena Horlemann-Trautmann (Universität Zürich, CH) [dblp]
- Jorn Justesen (Technical University of Denmark - Lyngby, DK) [dblp]
- Axel Kohnert (Universität Bayreuth, DE) [dblp]
- Margreta Kuijper (The University of Melbourne, AU) [dblp]
- P. Vijay Kumar (Indian Institute of Science, IN) [dblp]
- Michael Lentmaier (Lund University, SE) [dblp]
- Hans-Andrea Loeliger (ETH - Zürich, CH) [dblp]
- Felice Manganiello (Clemson University, US) [dblp]
- Muriel Médard (MIT - Cambridge, US) [dblp]
- Sihem Mesnager (University of Paris VIII, FR) [dblp]
- Olgica Milenkovic (University of Illinois - Urbana Champaign, US) [dblp]
- Katherine Morrison (University of Northern Colorado, US) [dblp]
- Joachim Rosenthal (Universität Zürich, CH) [dblp]
- Vladimir Sidorenko (Universität Ulm, DE) [dblp]
- Vitaly Skachek (University of Tartu, EE) [dblp]
- Roxana Smarandache (University of Notre Dame, US) [dblp]
- Patrick Solé (Télécom ParisTech, FR) [dblp]
- Emina Soljanin (Bell Labs - Murray Hill, US) [dblp]
- Alex Sprintson (Texas A&M University - College Station, US) [dblp]
- Vladimir D. Tonchev (Michigan Tech University - Houghton, US) [dblp]
- Bane Vasic (University of Arizona - Tucson, US) [dblp]
- Pascal Vontobel (HP Labs - Paolo Alto, US) [dblp]
- Judy L. Walker (University of Nebraska - Lincoln, US) [dblp]
- Wolfgang Willems (Universität Magdeburg, DE) [dblp]
- Oyvind Ytrehus (University of Bergen, NO) [dblp]
- Jiun-Hung Yu (ETH - Zürich, CH) [dblp]
Related Seminars
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