AF: SMALL: The Geometry of Integer Programming and Lattices

University Of Washington, Seattle WA

Investigators

Abstract

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.