CAREER: New Fundamentals in Coding Theory

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

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.