CAREER: New Fundamentals in Coding Theory

职业：编码理论的新基础

基本信息

批准号：
1844628
负责人：
Mary Wootters
金额：
$ 50万
依托单位：
Stanford University
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2019
资助国家：
美国
起止时间：
2019-02-01 至 2024-01-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1844628&HistoricalAwards=false
关键词：
CAREER New Fundamentals Coding Theory

项目摘要

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.

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