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

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

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.