NSF-BSF: AF: Small: Algorithms for Graph-Based Codes

NSF-BSF：AF：小型：基于图形的代码算法

基本信息

批准号：
2133154
负责人：
Mary Wootters
金额：
$ 50万
依托单位：
Stanford University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2022
资助国家：
美国
起止时间：
2022-03-01 至 2025-02-28
项目状态：
未结题

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

项目摘要

Error-correcting codes are a fundamental tool for protecting data in communication and storage. Graph-based codes – codes constructed and analyzed using tools from combinatorics and graph theory – are an important class of error-correcting codes. This project will develop new algorithms and techniques for graph-based codes. Such algorithms will have applications not only in communication and storage, but also in areas like algorithm design and complexity theory. This project also involves educational and outreach components, such as the development of publicly available teaching materials, including a series of YouTube lectures; and research opportunities for graduate and undergraduate students, with an emphasis on recruiting from groups underrepresented in computing. This project is an international collaboration, made possible through joint funding with the US-Israel Binational Science Foundation (BSF).In more detail, this project will develop techniques for list- and local-decoding of graph-based codes. In the standard unique decoding problem, a receiver wants to reconstruct a sender’s message exactly; in list-decoding, the receiver is allowed to produce a short list of possible messages; in local-decoding, the receiver is only responsible for a small portion of the original message. While graph-based codes are extremely well-studied for unique decoding, especially in the setting of stochastic errors, they are much less common for list-decoding or local-decoding. This project will make progress on two major open problems in coding theory, beyond graph-based codes: to achieve linear-time capacity-achieving list-decoding algorithms, and to perform local decoding with high rate and low query complexity. Moreover, progress in these areas will feed back into unique decoding, leading to uniquely decodable codes with extremely efficient decoding algorithms.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.

纠错码是保护通信和存储中的数据的基本工具——使用组合学和图论工具构建和分析的代码——是一类重要的纠错码。基于图的代码技术不仅可以应用于通信和存储，还可以应用于算法设计和复杂性理论等领域，该项目还涉及教育和推广部分，例如公开可用的教材的开发，包括。一系列 YouTube 讲座和研究机会；面向研究生和本科生，重点是从计算机领域代表性不足的群体中招募该项目是一项国际合作，通过与美国-以色列两国科学基金会 (BSF) 的联合资助而得以实现。更详细地说，该项目将开发技术。对于基于图的代码的列表和本地解码，在标准唯一解码问题中，接收者想要准确地重建发送者的消息；在列表解码中，允许接收者产生可能的消息的简短列表；在本地解码中，接收者只负责原始消息的一小部分，虽然基于图的代码对于独特的解码进行了非常深入的研究，特别是在随机错误的设置中，但它们对于列表解码或解码来说不太常见。本地解码。除了基于图的代码之外，该项目将在编码理论中的两个主要开放问题上取得进展：实现线性时间容量实现列表解码算法，以及以高速率和低查询复杂度执行本地解码。此外，这些领域的进展将反馈到独特的解码中，从而产生具有极其高效的解码算法的独特可解码代码。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力优点和更广泛的影响审查标准进行评估，被认为值得支持。