AF: SMALL: The Geometry of Integer Programming and Lattices

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

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.