AF: SMALL: The Geometry of Integer Programming and Lattices

在运筹学中最普遍的问题之一是整数规划，即优化线性函数的线性不等式和完整性。这是因为在实际应用中出现的大多数优化问题可以很容易地建模为这样的整数规划。尽管它很重要，但在已知算法之间存在很大的差距，这些算法在大约n^n的时间内工作，并且在十多年内没有改进，而基于指数时间假设的2^n阶下界。该项目旨在通过利用与格的连接来推进对这一重要问题的理论理解，以改进算法为目标。该项目还包括对研究生的培训。更详细地说，该项目的重点是从Kannan和Lovasz（1988）的一篇论文中提出的一个猜想，即格点自由凸集必须允许投影到一个子空间中，在该子空间中，当格是稀疏的时，该集合留下一个小阴影。在这个项目中要探索的其他方向是在多项式空间中工作的格问题的单指数时间算法。在这里，格本身就具有根本的重要性，并且是基于格的公钥加密方案的基础，例如错误学习，目前被认为是安全后量子加密的最佳前景。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估而被认为值得支持。

One of the most ubiquitous problems in operations research is integer programming, that is, optimizing a linear function subject to linear inequalities and integrality. The reason is that most optimization problems appearing in practical applications can be easily modeled as such an integer program. Despite its importance, there is a wide gap between known algorithms, which work in time roughly n^n with no improvement for over a decade, and lower bounds of the order 2^n based on the exponential time hypothesis. This project aims at advancing the theoretical understanding of this important problem by making use of the connection to lattices with the goal of improved algorithms. The project also incorporates training for graduate students.In more detail, the project focuses on a conjecture arising from a paper by Kannan and Lovasz (1988) that lattice-point free convex sets must admit a projection into a subspace where the set leaves a small shadow while the lattice is sparse. Other directions to be explored in this project are single-exponential time algorithms for lattice problems that work in polynomial space. Here lattices are of fundamental importance in their own right and are the basis for lattice-based public key cryptography schemes such as learning with errors, which are currently considered the best prospect for secure post-quantum cryptography.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.