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.

纠错码是保护通信和存储数据的基本工具。自 20 世纪 50 年代 Shannon 和 Hamming 的开创性工作以来，纠错码已在整个计算机科学和工程领域得到广泛应用，包括算法设计、复杂性理论和密码学。该项目的目标是在各种设置下开发极其高效的纠错码解码算法。除了解决算法编码理论中的基本问题外，本研究还将应用算法设计、复杂性理论和伪随机性。此外，该奖项还通过支持研究生和为本科生提供研究机会来促进教育。该项目是一项国际合作项目，通过与美国-以色列两国科学基金会 (BSF) 的联合资助而得以实现。该项目汇集了一名美国研究人员和一名以色列研究人员，他们都是算法编码理论方面的专家，并且有成功合作的历史。该项目开发了线性时间和亚线性时间算法，用于在以下情况下解码纠错码：这些代码以容量运行：也就是说，它们实现了最佳的组合和/或信息理论权衡。该方法是将代数、图论和信息论技术结合在一起。传统上，图论和信息论技术可用于开发用于解码的线性时间或近线性时间算法，而代数技术可用于开发亚线性时间算法。通过结合这些技术，该项目将在算法编码理论的基本问题上取得进展。该奖项反映了 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

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