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来进一步取得伪随身的进步，而且还将导致ECCS的进一步进展，因为伪随身界的应用突出了当前技术不足的ECC中的重要问题。项目支持研究生和本科教育和研究，以及学术界以外的外展活动。这是NSF-BSF的联合赠款；以色列Pi是本古里安大学的Dean Doron博士。这项研究有两个主要的推力。第一个推力与称为“清单恢复”的概念有关，该概念在对ECC的研究中变得越来越重要。但是，列表重新发现的最新进展仅在特定的参数制度中起作用，不幸的是，这并不是伪随身应用程序中感兴趣的参数制度。这项研究调查了列表恢复以外的参数制度。在此参数制度中研究列表恢复还具有算法应用程序，而不是编码理论或伪随身界。第二个推力与具有有效算法的二元代码以及速率（通信开销量）和距离（量度耐受噪声量的量度）之间的最佳权衡有关的经典问题。该项目利用清案的进展来取得这一困难问题的进展。该奖项反映了NSF的法定任务，并通过使用基金会的知识分子优点和更广泛的影响审查标准来评估，被认为是珍贵的支持。