During the Spring of 2024, the Simons Institute for the Theory of Computing at UC Berkeley hosted a thematic semester entitled “Error-Correcting Codes: Theory and Practice” organized by Sivakanth Gopi, Venkat Guruswami, Henry Pfister, Mary Wootters, and Gilles Zémor. As part of this program, the “Application-Driven Coding Theory Workshop” occurred during the week starting March 4th, 2024 and was co-organized by Krishna Narayanan and Henry Pfister.
The workshop was devoted to understanding key practical applications of coding theory both new and old. Some historical applications of coding theory include wireless communication, coding for magnetic/flash storage, and optical communication. Known applications receiving more attention these days include coding for DNA storage, coding for cryptography, and coding for quantum error correction/computing. Newer topics include coding for distributed computing (e.g., matrix multiplication), coding for distributed storage (locally recoverable codes), and coding for private information retrieval.
The workshop took place over the course of five days, each of which contained 6-7 talks. Overall there were 34 talks presented by 10 women and 24 men. Five of these talks were delivered online via zoom. A key goal was to bring many practitioners, who are associated more with engineering than the theory of computing, to the Institute to interact with theorists. In particular, 5 of the talks were given by engineers working at companies that build products which rely on error-correcting codes.
While each application has key motivating questions, we mention here a few that apply more widely. Several talks focused on the construction of short codes, understanding the performance limits of short codes, and algorithmic aspects on the design of decoding algorithms with moderate decoding complexity. This topic plays an important supporting role in wireless computing and quantum computing. New results on the design of codes with low error floors and the design of associated decoding algorithms that permit very high throughput implementations was also discussed. Such codes have applications in optical communications. Another important theme was how coding theory can be used to improve performance and save resources in data center computing. Important performance metrics for such coded systems were discussed.
A few talks focused on the emerging field of DNA storage and discussed the characteristics of sequencing systems that have a significant impact on the design of codes for DNA storage. Two talks focused on the role of machine learning in the design of codes and decoders, which is a topic of significant current interest. The use of coding for distributed computation has been a topic of recent interest. A few talks focused on the numerical stability and privacy guarantees that can be afforded by coded matrix multiplication schemes. The design of codes when the underlying matrices were sparse was addressed by multiple talks. One talk presented results on the design of codes when approximate computation suffices. Connections between coding theory and sparse recovery has been a topic of interest to both engineers and the theoretical computer science community. Recent results on the construction of graph based codes, such as low-density parity-check (LDPC) codes, for quantitative group testing and combinatorial problems in 1-bit compressed sensing were presented. Recent results on the analysis of the performance of polar codes for insertion-deletion channels was also presented.
Another set of talks focused on applications related to quantum information processing. One talk focused on using LDPC codes for quantum key distribution while another talk discussed using graph neural networks to decode quantum LDPC codes for error correction in quantum computing. Two related papers applied error correction to the problem of magic-state distillation for quantum computing. The first paper provided background material and described CSS-T codes while the second paper described a simplified characterization and provided new constructions for CSS-T codes.
One important goal of the workshop was to facilitate an understanding of new constraints that are imposed on coded systems and new performance metrics that are of interest in emerging applications. Several talks from the industry speakers as well semi-tutorial style talks from academic researchers enabled this.
We sincerely thank all the participants for their excellent contributions. In addition, the smooth operation of the workshop would not have been possible without dedicated assistance by the staff of the Simons institute.
