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阶的下限。该项目旨在通过利用与晶格的连接以改进算法的目的来推进对这一重要问题的理论理解。该项目还纳入了研究生的培训。此外，该项目的重点是由Kannan和Lovasz（1988）的论文引起的猜想，即lattice-Point Free凸面套装必须承认投影到子空间中，该集合会在该子空间中留下小阴影，而lattice则稀疏。该项目中要探索的其他方向是用于多项式空间中晶格问题的单个指数时间算法。在这里，格子本身至关重要，并且是基于晶格的公共密钥密码学方案的基础，例如学习错误的学习，目前被认为是安全后Quantum Cryptography的最佳前景。该奖项反映了NSF的法定任务，并通过该基金会的知识优点和广泛的影响来评估NSF的法定任务，并被认为是值得的支持。