NSF-BSF: AF: Small: Advancing Coding Theory Through the Lens of Pseudorandomness

NSF-BSF：AF：小：通过伪随机性的视角推进编码理论

基本信息

批准号：
2231157
负责人：
Mary Wootters
金额：
$ 60万
依托单位：
Stanford University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2023
资助国家：
美国
起止时间：
2023-05-01 至 2026-04-30
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2231157&HistoricalAwards=false
关键词：
NSF BSF AF Small Advancing

项目摘要

The goal of this project is to simultaneously advance both the theory of error correcting codes (ECCs) and pseudorandomness by exploring connections between them. ECCs are a fundamental tool to protect data from noise, and the past decade has seen many breakthroughs, both theoretical and practical. Pseudorandomness is the study of deterministic objects that “behave like random objects,” and is a fundamental area in theoretical computer science. Connections between ECCs and pseudorandomness have been noted before, and indeed there is a rich interplay between the two areas. However, the time is right to revisit this connection in light of recent breakthroughs in ECCs. In doing so, this project leads not only to further progress in pseudorandomness by leveraging ECCs, but will also lead to further progress in ECCs, as applications in pseudorandomness highlight important questions in ECCs where current techniques fall short. This project supports graduate and undergraduate education and research, as well as outreach beyond academia. This is a joint NSF-BSF grant; the Israeli PI is Dr. Dean Doron of Ben Gurion University.There are two main thrusts of this research. The first thrust has to do with a notion called “list-recovery,” which has become increasingly important in the study of ECCs. However, recent progress in list-recovery has worked only in a particular parameter regime, which unfortunately is not the parameter regime of interest in pseudorandomness applications. This research investigates list-recovery beyond the parameter regime that is currently understood. Studying list recovery in this parameter regime also has algorithmic applications beyond either coding theory or pseudorandomness. The second thrust has to do with the classical problem of obtaining binary codes with efficient algorithms and the optimal trade-offs between rate (the amount of communication overhead) and distance (a measure of the amount of noise tolerated). This project leverages progress on list-recovery to make progress on this difficult problem.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.

该项目的目标是通过探索纠错码 (ECC) 和伪随机性理论之间的联系，同时推进它们之间的联系。ECC 是保护数据免受噪声影响的基本工具，在过去的十年中，无论是理论还是伪随机性都取得了许多突破。伪随机性是对“表现得像随机对象”的确定性对象的研究，是理论计算机科学的一个基本领域。ECC 和伪随机性之间的联系以前已经被注意到，而且确实存在丰富的联系。然而，鉴于 ECC 最近取得的突破，现在是重新审视这种联系的时候了。这样做，该项目不仅会利用 ECC 在伪随机性方面取得进一步进展，而且还将导致在伪随机性方面取得进一步进展。 ECC，作为伪随机性的应用，突出了 ECC 中当前技术不足的重要问题。该项目支持研究生和本科生的教育和研究，以及以色列 PI 的联合资助。本古里安大学的 Dean Doron 博士表示，这项研究有两个主要目标。第一个目标与“列表恢复”的概念有关，该概念在 ECC 的研究中变得越来越重要。但是，最近取得了进展。列表恢复仅在特定的参数范围内起作用，不幸的是，这不是伪随机性应用中感兴趣的参数范围。这项研究研究了当前理解的参数范围之外的列表恢复。超越编码理论或伪随机性的算法应用第二个推动力与使用有效算法获取二进制代码的经典问题以及速率（通信开销量）和距离（通信量量的度量）之间的最佳权衡有关。该项目利用列表恢复方面的进展来解决这一难题。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。