CAREER: Computationally Efficient Error-Correcting Codes and Their Applications

这项研究的目的是提高纠错码的计算效率，并将这一努力中的技术应用于计算和信息论的其他问题。纠错码是所有电子通信系统的重要组成部分。最近已经开发了可以非常有效地编码和解码的纠错码的新结构。本研究的目标是通过以下方式扩展这一初步工作：提高基于先前开发的码的显式构造纠错码的容错性和速度。开发能够证明随机构造的质量的算法。使用相关技术提高对信息论和电子通信至关重要的其他任务的计算效率。开发代码的高质量实现，这将使工程师更容易测试这些代码在他们自己的应用领域中的表现。拟议调查的教育目标范围更广。它们涉及到设计课程，向研究生传授这项研究所依据的更大的数学框架。这些课程应该会吸引来自数学和计算机科学的学生学习新的迷人的方法，在这些方法中，数学的思想可以被应用到解决计算机科学中的重要问题。这些课程旨在教授如何在研究中建立联系，并为他们提供许多成熟的联系领域。最终，这些课程将教会学生首席研究员研究方法的另一个基本要素：在数学研究中使用计算实验。他们将学习如何使用计算机实验来制作和测试组合猜想。当他们开始将计算机视为一种可以帮助他们进行研究的工具时，他们将不可避免地对计算算法的效率感到担忧，并获得直觉，即哪些数学思想可能会导致实际的算法。

The goals of this research are to improve the computational efficiency of error-correcting codes and to apply techniques from this effort to other problems of computation and information theory. Error-correcting codes are essential components of all electronic communication systems. New constructions for error-correcting codes that could be encoded and decoded very efficiently have recently been developed. The objectives of this research are to extend this initial work by: Improving the error-tolerance and speed of the explicit constructions of error-correcting codes based upon previously developed codes. Developing algorithms that can certify the quality of the randomized constructions. Using related techniques to improve the computational efficiency of other tasks vital to information theory and electronic communication. Developing quality implementations of the codes that will make it easier for engineers to test how these codes would perform in their own application areas. The educational goals of the proposed investigation are broader in scope. They involve the design of classes that teach graduate students about the larger mathematical framework on which this research rests. These classes should attract students from mathematics as well as computer science to learn about the new fascinating ways in which ideas from mathematics can be applied to solve important problems in computer science. These classes are designed to teach how connections in research are made as well as provide them with many areas ripe for connection. Eventually, these classes will teach the students another essential element of the principal investigator's research methodology: that of using computational experiments in mathematical research. They will learn how one can use computer experiments to make and test combinatorial conjectures. As they begin to see the computer as a tool that can aid them in their own research, they will inevitably become concerned with the efficie ncy of computational algorithms and gain intuition for which mathematical ideas might result in practical algorithms.***