CCF-BSF: AF: CIF: Small: Low Complexity Error Correction

纠错码是通信和存储中保护数据的基本工具。自20世纪50年代Shannon和Hamming的开创性工作以来，纠错码在整个计算机科学和工程中得到了广泛的应用，包括在算法设计、复杂性理论和密码学中。该项目的目标是开发在各种环境下用于纠错码的极其高效的译码算法。除了解决算法编码理论中的基本问题外，这项研究还将应用于算法设计、复杂性理论和伪随机性。此外，该奖项通过支持研究生和为本科生提供研究机会来促进教育。该项目是一项国际合作，通过与美国-以色列双国科学基金会(BSF)的联合资助而成为可能。该项目汇集了一名美国研究人员和一名以色列研究人员，他们都是算法编码理论方面的专家，并且有成功合作的历史。该项目开发了线性时间和次线性时间算法，用于在纠错码达到最大容量的情况下解码这些码：也就是说，它们达到了可能的最佳组合和/或信息论折衷。方法是将代数、图论和信息论技术结合起来。传统上，图论和信息论技术用于开发线性时间或近线性时间的译码算法，而代数技术用于开发次线性时间算法。通过结合这些技术，该项目将在算法编码理论的基本问题上取得进展。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Error correcting codes are a fundamental tool for protecting data in communication and storage. Since the seminal works of Shannon and Hamming in the 1950s, error correcting codes have found uses throughout computer science and engineering, including in algorithm design, complexity theory, and cryptography. The goal of this project is to develop extremely efficient decoding algorithms for error correcting codes, in a variety of settings. In addition to addressing fundamental problems in algorithmic coding theory, this research will have applications algorithm design, complexity theory and pseudorandomness. Further, this award advances education by supporting graduate students and by providing research opportunities for undergraduates. This project is an international collaboration, made possible through joint funding with the US-Israel Binational Science Foundation (BSF). The project brings together one US investigator and one Israeli investigator, both of whom are experts in algorithmic coding theory, and who have a history of successful collaboration.This project develops linear-time and sublinear-time algorithms for decoding error correcting codes in scenarios where these codes operate at capacity: that is, where they attain the best possible combinatorial and/or information-theoretic trade-offs. The approach is to bring together algebraic, graph-theoretic, and information-theoretic techniques. Traditionally, graph-theoretic and information-theoretic techniques have been useful in developing linear-time or near-linear-time algorithms for decoding, while algebraic techniques have been useful in developing sublinear-time algorithms. By combining these techniques, this project will make progress on fundamental questions in algorithmic coding theory.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.