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

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

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.