CAREER: Error-Correcting Codes, Complexity Theory and Pseudorandomness

职业：纠错码、复杂性理论和伪随机性

• 批准号: 1253886
• 负责人: Swastik Kopparty
• 金额: $ 49.26万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-02-01 至 2019-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1253886&HistoricalAwards=false
• 关键词: CAREER; Error; Correcting; Codes; Complexity

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.

由Shannon和Hamming提出的经典纠错码理论已经发展成为一门蓬勃发展的学科，并在通信和存储系统的设计中产生了巨大的影响。 然而，纠错码的更现代的方面，包括与复杂性理论和伪随机性相关的方面，已经落后，并且许多挑战和问题还没有得到很好的理解。 该项目旨在通过系统地探索在本地解码，本地测试，列表解码和本地列表解码领域中可以实现的内容，并通过探索复杂性理论和伪随机性中的含义来纠正这种情况。 本计画主要研究支援次线性时间错误侦测、次线性时间错误修正与有效列表译码的错误修正码的新构造，以及其在计算复杂度理论与伪随机性领域的应用。该项目建立在PI最近取得的几项进展的基础上，例如首次允许亚线性时间纠错的新的高速率纠错码的构建。该项目的教育部分将涉及对打算从事研究的初级研究人员的指导和教育，以及编制和传播新的课程材料和广泛传播这项研究成果。