CAREER: Error-Correcting Codes, Complexity Theory and Pseudorandomness

香农和汉明的经典纠错码理论已经发展成为一个蓬勃发展的学科，并对通信和存储系统的设计产生了巨大的影响。然而，纠错码的更现代的方面，包括那些与复杂性理论和伪随机性相关的方面，已经落后了，许多挑战和问题没有得到很好的理解。本项目旨在通过系统地探索在局部解码、局部测试、列表解码和局部列表解码领域可以实现的目标，以及通过探索复杂性理论和伪随机性中的含义，来纠正这种情况。本项目拟研究支持亚线性时间错误检测、亚线性时间错误纠正和高效列表解码的纠错码的新结构，以及它们在计算复杂性理论和伪随机领域的应用。该项目建立在PI最近取得的几项进展的基础上，例如构建新的高速率纠错码，首次允许亚线性时间纠错。这个项目的教育部分将包括指导和教育有意从事研究事业的初级研究人员，以及编制和传播新的课程材料和广泛介绍这项研究的结果。

The classical theory of error-correcting codes by Shannon and Hamming has developed into a flourishing subject, and has been hugely influential in the design of communication and storage systems. However, the more modern aspects of error-correcting codes, including those relevant to complexity theory and pseudorandomness, have lagged behind, and many challenges and problems are not well understood. This project aims to remedy this situation by systematically exploring what can be achieved in the realm of local-decoding, local-testing, list-decoding and local list-decoding, and by exploring the implications of this in complexity theory and pseudorandomness. This project proposes to investigate new constructions of error-correcting codes supporting sublinear-time error-detection, sublinear-time error-correction and efficient list-decoding, as well as their applications in the areas of computational complexity theory and pseudorandomness. The project builds upon several recent advances made by the PI, such as the construction of new high rate error-correcting codes allowing, for the first time, sublinear-time error-correction.The educational component of this project will involve the mentoring and education of junior researchers who intend to pursue a career in research, as well as the development and dissemination of new course materials and broadly accessible presentations of the results of this research.