Friday, May 14

Computational Aspects of Coding Theory

(Invited Minisymposium)

4:15 PM-6:15 PM
Room: Capitol Center

Computational efficiency is a central issue in the design of error correcting codes. Codes, conversely, serve to protect computations against noise, a role that has a renewed significance in the field of quantum computation. The minisymposium will feature both directions of this interaction between algorithms and coding theory.

The first three speakers in this minisymposium will discuss highly efficient coding algorithms, and codes that are designed with these algorithms in mind; algorithms which can frequently decode messages corrupted slightly beyond the distance bound of a code: this is possible since most such messages are still closer to the correct codeword than to any other; and algorithms and hardness results concerning the construction of minimal trellises, widely used for communications (e.g. in modems). The last speaker will discuss quantum error correcting codes. These are closely related to classical codes, and can be used in the design of quantum computers to protect against the effects of inaccuracy and decoherence -- the most fundamental challenges to implementation of these devices.

Organizer: Leonard J. Schulman
Georgia Institute of Technology

4:15-4:40 Low Complexity Low-Density Parity Check Codes
Amin Shokrollahi, Bell Laboratories, Lucent Technologies
4:45-5:10 Positive and Negative Computational Results on Minimal Trellis Construction
Vijay V. Vazirani, Georgia Institute of Technology
5:15-5:40 List Decoding Algorithms for Algebraic Codes
Madhu Sudan, Massachusetts Institute of Technology
5:45-6:10 Error Correcting Codes in Quantum Computation
Peter Shor, AT&T Laboratories Research

AN99 Home


Program Updates

Speaker Index




tjf, 1/19/99, MMD, 1/27/99