CAREER: Efficiency Considerations in List Decoding and Pseudorandomness Theory

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

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.