{"id":"arxiv/2610.10911","url":"https://arxiv.org/abs/2610.10911","tags":["math.OC","cs.CC","cs.DM"],"score":0,"title":"Integer programming on polytopes of Chvátal rank one is as hard as lattice problems","domain":"math.OC","source":"arxiv","authors":["Alberto Del Pia"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-07","reactions":{}}