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的错误校正代码的经典理论已发展为繁荣的主题，并且在通信和存储系统的设计中具有极大的影响力。 但是，错误纠正错误的代码的更现代方面，包括与复杂性理论和伪随机性相关的代码，已经落后了，许多挑战和问题尚未得到充分理解。 该项目旨在通过系统地探索在局部编码，局部测试，列表编码和本地列表编码的领域中可以实现的目标，并通过探索这种含义在复杂性理论和伪随机性中的含义。 该项目建议研究支持跨度时间误差检测，sublrinear-time误差校正和有效列表编码的新的误差校正代码的新结构，以及它们在计算复杂性理论和伪符合性领域的应用。该项目建立在PI最新进展的基础上，例如建立新的高率误差校正验证代码，首次允许SublineArime-Pime误差纠正。该项目的教育组成部分将涉及对研究人员的指导和教育，这些研究人员打算从事研究领域的职业，以及对新课程的发展和开发新的材料和开发材料的介绍，并介绍了这一结果。