Complexity and Algorithms of Decoding Algebraic Codes

信号在远距离传输时很可能会被损坏。纠错码就是为了解决这个问题而设计的，所以我们今天看到的现代通信是可能的。代数编码在数学上是有趣的，它们构成了编码理论及其应用的支柱。许多代数代码的最佳算法非常强大，但不太实用。此外，这些代码的确切解码复杂性还没有得到很好的理解，包括简单但极其重要的里德-所罗门代码。该项目将努力识别解码代数代码的复杂性，并为大量代数代码设计更有效的算法。主要的焦点是具有自然参数的代数码。因此，这些自然密码的复杂性结果与通信实践更相关。预计该项目将导致一系列实质性的新结果，将编码理论、计算机科学和数学联系起来。该项目还有望在这一跨学科研究领域开发研究生课程和培养学生。

A signal, when transfered over a long distance, is likely to be corrupted. Error-correcting codes have been designed to solve this problem, so modern communications are possible as we see today. Algebraic codes are mathematically interesting and intriguing, and they form the backbone of coding theory and its applications. The best algorithms for many algebraic codes are very powerful but not very practical. Also, the exact decoding complexity is not well understood for these codes, including the simple but extremely important Reed-Solomon codes. The project will strive to identify the complexity of decoding algebraic codes and to design more efficient algorithms for a large class of algebraic codes. The main focus is on algebraic codes with natural parameters. The complexity results for these natural codes thus are more relevant to communication practice. It is expected that the project will lead to a number of substantial new results linking coding theory, computer sciences and mathematics. The project is also expected to develop graduate courses and train students in this cross-disciplinary research area.