CAREER: Efficiency Considerations in List Decoding and Pseudorandomness Theory

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

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.