August 25 – 30 , 2013, Dagstuhl Seminar 13351
1 / 2 >
For support, please contact
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.
Creative Commons BY 3.0 Unported license
Hans-Andrea Loeliger, Emina Soljanin, and Judy L. Walker
Dagstuhl Seminar Series
- Algorithms And Complexity
- Algebraic Techniques
- Algebraic coding theory
- Complexity theory
- Graph theory
- Graph based codes
- Information theory
- Randomized algorithms
- Data distribution