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

CCF-BSF：AF：CIF：小：低复杂性纠错

基本信息

批准号：
1814629
负责人：
Mary Wootters
金额：
$ 50万
依托单位：
Stanford University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-10-01 至 2021-10-31
项目状态：
已结题

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

项目摘要

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.

错误纠正代码是保护通信和存储中数据的基本工具。自从1950年代香农和锤打的开创性作品以来，错误纠正代码在整个计算机科学和工程中都发现了用途，包括算法设计，复杂性理论和密码学。该项目的目的是在各种设置中开发出极有效的解码算法，以纠正错误代码。除了解决算法编码理论中的基本问题外，这项研究还将具有应用算法设计，复杂性理论和伪随机性。此外，该奖项通过支持研究生并为大学生提供研究机会来提高教育。该项目是一项国际合作，通过与美国 - 以色列双原则科学基金会（BSF）的共同资助使得成为可能。该项目汇集了一位美国调查员和一名以色列研究者，他们都是算法编码理论的专家，并且具有成功协作的历史。该项目开发了线性时间和sublinear-time算法，用于解码这些代码在这些方案中在这些方案中纠正这些代码在这些方案中纠正这些代码，这些代码在这些方案中运行，在这些方案中，在这些方案中运行的是，在这些方案中，他们在其中的最佳和/或commighors and/commighor commighors和/或/或/或/或/或/或/或/或/或/或/或/或/或/或/或/或或/或/或/或/或/或/或或/或/或或/或或或或或或或或或或或或或或位几所所为所提供所在所为所提供所在所提供所在所提供所代码所致所致所致而或所在为所致而言。该方法是将代数，图理论和信息理论技术汇总在一起。传统上，图理论和信息理论技术对于开发用于解码的线性时间或接近线性的算法很有用，而代数技术对于开发均方根时算法很有用。通过结合这些技术，该项目将在算法编码理论的基本问题上取得进展。该奖项反映了NSF的法定任务，并使用基金会的知识分子优点和更广泛的审查标准，认为值得通过评估来获得支持。

项目成果

期刊论文数量（12）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Sharp Threshold Rates for Random Codes

随机码的急剧阈值率

DOI：
10.4230/lipics.itcs.2021.5
发表时间：
2021
期刊：
Leibniz international proceedings in informatics
影响因子：
0
作者：
Guruswami, Venkatesan;Mosheiff, Jonathan;Resch, Nicolas;Silas, Shashwat;Wootters, Mary
通讯作者：
Wootters, Mary

Bounds for List-Decoding and List-Recovery of Random Linear Codes

随机线性码的列表解码和列表恢复的界限

DOI：
10.4230/lipics.approx/random.2020.9
发表时间：
2020
期刊：
Leibniz international proceedings in informatics
影响因子：
0
作者：
Guruswami, Venkatesan;Li, Ray;Mosheiff, Jonathan;Resch, Nicolas;Silas, Shashwat;Wootters, Mary
通讯作者：
Wootters, Mary

On List Recovery of High-Rate Tensor Codes

高速张量代码的列表恢复

DOI：
10.4230/lipics.approx-random.2019.68
发表时间：
2019
期刊：
Leibniz international proceedings in informatics
影响因子：
0
作者：
Kopparty, Swastik;Resch, Nicolas;Ron-Zewi, Noga;Saraf, Shubhangi;Silas, Shashwat
通讯作者：
Silas, Shashwat

Local List Recovery of High-Rate Tensor Codes and Applications

高速张量代码的本地列表恢复及应用