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.