Collaborative Research: 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