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.