CAREER: Efficiency Considerations in List Decoding and Pseudorandomness Theory

职业：列表解码和伪随机性理论中的效率考虑

• 批准号: 2236931
• 负责人: Mahdi Cheraghchi Bashi Astaneh
• 金额: $ 65.5万
• 依托单位: Regents of the University of Michigan - Ann Arbor
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-09-01 至 2028-08-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2236931&HistoricalAwards=false
• 关键词: CAREER; Efficiency; Considerations; List; Decoding

Since the pioneering work of Claude Shannon to formulate a mathematical theory of communication in 1948, the theory of error-correcting codes has enabled the practical deployment of reliable and large-scale computer and communication systems. Today, coding theory is used in virtually all aspects of computing devices: for the data exchange between different chips inside a computer, data transmission over a cable, data retention in storage devices, internet communications, household smart devices, and wireless communications in cell phones, to name a few. Modern demands for large-scale computation call for pushing the state of the art in coding techniques much further than originally envisioned by Shannon’s breakthrough, and this project aims to further that goal. The educational plans cover a broad range of contributions ranging from engagement with K-12 students, undergraduate and graduate level education, to public outreach.To pursue the broader vision of this project, the investigator focuses on the intricate connections between coding theory, particularly list decoding of error-correcting codes, and the theory of pseudorandomness at the core of computer science. Like codes, fundamental pseudorandom objects such as pseudorandom generators and randomness extractors have emerged from practical motivations, such as applications in cryptography and randomized algorithms. Furthermore, deep connections are known between these objects and error-correcting codes, particularly list decodable codes. As a result, the state of the art in both pseudorandomness and list decoding is, to a great extent, based on the same mathematical foundations. Even though the current constructions achieve remarkable guarantees in theory, they are far from the originally intended practical use. This project pursues the insight that the disconnect from practice is not merely an engineering challenge, but is mainly due to gaps in the theoretical understanding of the fundamental notions. The investigator has identified the shortcomings in theory and aims to pave the way toward optimal constructions of error-correcting codes and related pseudorandom objects that are also amenable to practical deployment.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.

自 1948 年克劳德·香农 (Claude Shannon) 开创性地提出了通信数学理论以来，纠错码理论使得可靠的大规模计算机和通信系统得以实际部署。如今，编码理论几乎应用于各个方面。计算设备的应用：计算机内部不同芯片之间的数据交换、电缆数据传输、存储设备中的数据保留、互联网通信、家庭智能设备以及手机中的无线通信等等现代需求。 - 推动状态的规模计算调用编码技术的艺术发展比香农最初设想的突破要远得多，该项目旨在进一步推进这一目标，教育计划涵盖广泛的贡献，从 K-12 学生的参与、本科生和研究生教育到公共教育。为了实现该项目的更广泛愿景，研究人员重点关注编码理论（特别是纠错码的列表解码）与计算机科学核心的伪随机性理论（如代码、基本伪随机对象等）之间的复杂联系。作为伪随机生成器随机性提取器是出于实际动机而出现的，例如在密码学和随机算法中的应用。此外，这些对象和纠错码之间的深层联系是已知的，特别是列出可解码的代码，因此，伪随机性是最先进的。和列表解码在很大程度上基于相同的数学基础，尽管当前的构造在理论上取得了显着的保证，但它们与最初预期的实际用途相距甚远。仅仅这是一个工程挑战，但主要是由于对基本概念的理论理解存在差距，研究者已经识别出理论上的缺陷，旨在为纠错码和相关伪随机对象的最佳构造铺平道路。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。