CAREER: New Fundamentals in Coding Theory

编码理论是对纠错码的研究，纠错码对数据进行编码以保护其免受噪声的影响。纠错码从20世纪40年代开始研究；今天，从硬盘驱动器到卫星通信，它们被广泛使用。这项研究的目标是在编码理论在计算机科学、数学和工程中的新应用的启发下，提出并攻击编码理论中的新的基本问题。在回答这些问题时，这个项目不仅解决了应用领域，还发展了洞察力来解决编码理论中长期悬而未决的问题。这个项目是跨学科的，包括一个旨在将不同背景的学生聚集在一起的协同教育计划。该教育计划包括斯坦福大学研究生和本科课程的课程开发，以及研究生的培训和本科生的研究机会。更详细地说，该项目着眼于分布式存储、密码学、算法设计和伪随机性方面的应用，将四个新镜头引入编码理论。这些镜头中的每一个都在编码理论中提出了新的基本问题。这些问题大致分为“局部性”和“列表解码”两类。非正式地，局部性指的是仅从少量编码数据解码一小部分原始数据的能力。列表解码是指这样一种设置，其中存在太多的噪声，以至于无法唯一地确定原始数据，并且解码器必须尽其所能将可能性缩小到相对较短的列表。通过回答这些新的基本问题，这项研究不仅将在激励应用方面取得进展，还将发展新的理论，阐明纠错码中位置和列表译码的结构。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Coding theory is the study of error-correcting codes, which encode data to protect it from noise. Error-correcting codes have been studied since the 1940s; today, they are used everywhere from hard drives to satellite communication. This goal of this research is to pose and attack new fundamental questions in coding theory, inspired by new applications of coding theory across computer science, mathematics, and engineering. In answering these questions, this project not only addresses the application areas, but also develops insights to tackle long-standing open questions in coding theory. This project is interdisciplinary, and includes a synergistic education plan aimed at bringing together students from different backgrounds. The education plan incorporates course development of both graduate and undergraduate courses at Stanford University as well as training for graduate students and research opportunities for undergraduates.In more detail, this project focuses on four new lenses into coding theory, motivated by applications in distributed storage, cryptography, algorithm design and pseudorandomness. Each of these lenses raises new fundamental questions in coding theory. These questions fall broadly into the categories of "locality" and "list-decoding." Informally, locality refers to the ability to decode a small part of the original data from only a small amount of encoded data. List-decoding refers to the setting where there is so much noise that the original data cannot be uniquely determined, and the decoder must do the best it can to narrow the possibilities to a relatively short list. By answering these new fundamental questions, this research will both make progress on the motivating applications and will also develop new theory illuminating the structure of locality and list-decoding in error correcting codes.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.