CAREER: Efficiency Considerations in List Decoding and Pseudorandomness Theory

自从1948年克劳德·香农提出通信的数学理论以来，纠错码理论使可靠和大规模的计算机和通信系统的实际部署成为可能。今天，编码理论几乎应用于计算设备的所有方面：计算机内部不同芯片之间的数据交换、电缆上的数据传输、存储设备中的数据保留、互联网通信、家用智能设备以及手机中的无线通信，仅举几例。现代对大规模计算的需求要求将编码技术的最先进水平推向比Shannon的突破最初设想的更远的地方，本项目旨在进一步实现这一目标。教育计划涵盖了广泛的贡献，从与K-12学生的接触，本科生和研究生水平的教育，到公共外游。为了追求这个项目的更广泛的愿景，研究人员专注于编码理论，特别是纠错码的列表译码，和计算机科学核心的伪随机性理论之间的复杂联系。像代码一样，基本伪随机对象，如伪随机生成器和随机性抽取器，也是出于实际动机而出现的，例如在密码学和随机化算法中的应用。此外，这些对象和纠错码之间的深层联系是已知的，尤其是列表可译码。因此，伪随机性和列表解码的技术状态在很大程度上都是基于相同的数学基础。尽管目前的建筑在理论上取得了显著的保证，但它们与最初的实际用途相去甚远。这个项目追求的洞察力是，与实践的脱节不仅是一个工程挑战，而且主要是由于对基本概念的理论理解存在差距。研究人员已经发现了理论上的不足，并旨在为纠错码和相关伪随机对象的最佳构造铺平道路，这些对象也适合实际部署。这一奖项反映了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.