EAGER: Complexity of Computation on Codes and Lattices

纠错码和点格是科学和工程（例如，在通信和存储系统、电子电路设计和安全密码系统中）的中心原语。这些代数原语也与理论计算机科学和数学中的基本问题有着深刻的联系。尽管由于其实际意义而被广泛研究，但许多关于此类代数对象的计算问题仍然广泛开放。因此，提高我们对不同计算模型中代码和格的能力和局限性的理解将对许多应用领域产生重大影响。本项目概述的研究计划旨在通过提出新的计算方法和模型来解决现代密码学和编码理论核心的算法挑战。该项目旨在通过利用代数和几何方面，以及结构和对称的概念，揭示代码和晶格之间以及特定于它们的计算问题之间有影响力的相互联系。这个项目的成果将被整合到新课程中，以及本科和研究生的研究中。该项目还将帮助支持普渡大学的一个活跃的理论小组，并帮助培养学生在未来的职业生涯中具有竞争力。具体来说，提议的项目将推动计算问题的发展，这些问题可以抽象为纠错码和点格环境中最近邻搜索问题的变体。针对这些问题的有效算法可能在存储系统的应用中发挥变革性作用，而硬度结果可能影响格基加密的安全性。该项目还将侧重于点阵问题的次线性计算模型的概念化和形式化，目标是克服代码次线性模型研究中的已知障碍。格问题的超高效算法可以应用于数学优化和基于格的通信。该项目将探索和发展不同领域的见解，包括编码和信息论、次线性算法、密码学和优化。

Error-correcting codes and point lattices are central primitives in science and engineering (e.g., in communication and storage systems, electronic circuit design, and secure cryptographic systems). These algebraic primitives also have deep connections with fundamental questions in theoretical computer science and mathematics. Despite being intensely studied for their practical relevance, many computational problems on such algebraic objects remain widely open. Consequently, improving our understanding of the power and limitations of codes and lattices in diverse computational models will have a significant impact in many application domains. The research plan outlined in this project aims to address algorithmic challenges at the heart of modern cryptography and coding theory, by proposing novel approaches and models of computation. The project aims to reveal influential interconnections between codes and lattices, and between the computational problems specific to them, by leveraging algebraic and geometric aspects, together with notions of structure and symmetry. The outcomes of this project will be integrated in new courses, and in undergraduate and graduate research. This project will also help support an active theory group at Purdue University, and help train students to become competitive in their future careers. Specifically, the proposed project will advance the state of the art of computational problems that can be abstracted as variants of nearest-neighbor search problems in the context of error-correcting codes and point lattices. Efficient algorithms for these problems could play a transformative role in applications to storage systems, and hardness results could impact the security of lattice-base cryptography. The project will also focus on conceptualizing and formalizing models of sublinear computation for lattice problems, with the goal of overcoming known barriers from the study of sublinear models for codes. Super-efficient algorithms for lattice problems could have applications in mathematical optimization, and in lattice-based communication. The project will explore and develop insights from diverse areas including coding and information theory, sublinear algorithms, cryptography, and optimizations.