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.

自克劳德·香农（Claude Shannon）在1948年形成数学交流理论的开创性工作以来，错误校正代码的理论使可靠的大规模计算机和通信系统的实际部署能够实施。如今，编码理论几乎在计算设备的各个方面都使用：对于计算机内的不同芯片之间的数据交换，电缆上的数据传输，存储设备中的数据保留，Internet通信，家用智能设备以及手机中的无线通信，仅举几例。对大规模计算的现代需求要求推动编码技术中的最新技术的状态，远远超过了香农的突破最初设想的，该项目旨在进一步实现这一目标。教育计划涵盖了从与K-12学生的互动，本科和研究生级教育到公共宣传的广泛贡献，为了追求对该项目的更广泛的愿景，研究人员专注于编码理论之间的复杂联系，尤其是列出了对错误纠正校正代码的解码，以及对计算机科学核心科学核心核心的理论。像代码一样，基本的伪随机对象（例如伪随机生成器和随机性提取器）也来自实际动机，例如在加密和随机算法中的应用。此外，这些对象和错误校正的代码之间已知深度连接，尤其是列出可解码的代码。结果，基于相同的数学基础，伪随机性和列表解码的最新状态在很大程度上是基于相同的基础。即使当前的结构在理论上获得了显着的保证，但它们远非原始预期的实际用途。该项目追求一个见解，即与实践的脱节不仅是工程挑战，而且主要是由于对基本笔记的理论理解差距。研究者已经确定了理论上的缺点，并旨在为错误纠正的代码和相关的伪随机物体的最佳结构铺平道路，这些对象也适用于实际部署。该奖项反映了NSF的法定任务，并通过使用该基金会的知识分子优点和广泛的影响来评估NSF的法定任务，并被认为是珍贵的支持。