权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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）共同资助。更详细地说，这个项目将开发基于图的代码的列表和本地解码技术。在标准的唯一解码问题中，接收方希望准确地重构发送方的信息；在列表解码中，允许接收方生成可能消息的短列表；在本地解码中，接收方只负责原始消息的一小部分。虽然基于图的代码在惟一解码方面得到了非常好的研究，特别是在随机错误的设置中，但它们在列表解码或局部解码方面却不太常见。该项目将在编码理论的两个主要开放问题上取得进展，超越基于图的编码：实现线性时间容量实现列表解码算法，以及以高速率和低查询复杂度执行局部解码。此外，这些领域的进展将反馈到唯一解码，导致具有极其高效的解码算法的唯一可解码代码。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。