AF: SMALL: The Geometry of Integer Programming and Lattices

AF：小：整数规划和格的几何

• 批准号: 2318620
• 负责人: Thomas Rothvoss
• 金额: $ 45万
• 依托单位: University of Washington
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-08-01 至 2026-07-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2318620&HistoricalAwards=false
• 关键词: AF; SMALL; Geometry; Integer; Programming

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.

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