Integer programming problems with one-step cuts are as hard as lattice decoding
Integer programming on polytopes of Chvátal rank one is as hard as lattice problems
Computational ComplexityDiscrete Mathematics
Summary
Integer programming involves finding whole number solutions inside certain geometric shapes, called polytopes. Some polytopes become simple after one round of a standard cutting method, leading to a question of how hard it is to find integer solutions there. The authors show that even these seemingly simple shapes still hide problems just as hard as long-standing lattice puzzles important for cryptography. Their work connects these shapes' geometry to difficult problems that computers struggle to solve efficiently.
What this means in practice
- •For cryptography engineers: Recognize that polynomial-time integer programming approaches for one-step cut polytopes would break widely believed cryptographic assumptions, guiding secure system design.
- •For optimization software developers: Understand limits on efficiency gains for integer programming solvers when working with polytopes having Chvátal rank one, to better target heuristics or approximation methods.
A theory result. No direct application yet.
Authors
Alberto Del Pia
Abstract
A rational polyhedron has Chvátal rank at most one if a single round of Chvátal-Gomory cuts yields its integer hull. For such polyhedra, integer feasibility is in NP $\cap$ coNP by a result of Boyd and Pulleyblank from the early 1980s, so it is unlikely to be NP-hard. Whether it is polynomial has remained open since then. We answer this question negatively, under either of two standard assumptions from lattice-based cryptography. First, a polynomial-time algorithm for this problem would solve bounded distance decoding with polynomial factors in deterministic polynomial time, contradicting a widely believed conjecture. Second, assuming the hardness of learning with errors, an average-case analogue of bounded distance decoding, the problem is also hard on average, for an efficiently samplable distribution of polytopes. Both results rest on an elementary sufficient condition: a polyhedron has Chvátal rank at most one if its width is less than one along every row of some unimodular matrix. For our polytopes, such a matrix exists but is hard to find.