PaperlayerView exact revision on arXiv

Source-linked AI summary

Integer programming on polytopes of Chv\'atal rank one is as hard as lattice problems

Alberto Del Pia

arXiv:2610.10911v1math.OCcs.CCcs.DM

TL;DR

Whether integer feasibility is polynomial-time decidable for polyhedra whose Chvátal closure equals their integer hull has remained open. The paper gives conditional reductions from worst-case bounded distance decoding and average-case learning with errors, using a width condition that ensures Chvátal rank at most one. Thus, polynomial-time feasibility algorithms would yield algorithms for lattice problems under the stated hardness assumptions.

  • Problem

    Whether integer feasibility is polynomial-time decidable when P′ = PI remains open, even though the promise problem is in NP ∩ coNP.

    Source: §1 · pp. 1–2

  • Method

    The reductions construct polytopes whose width is less than one along the rows of a suitable unimodular matrix, ensuring P′ = PI.

    Source: §1 · p. 4

  • Results

    A polynomial-time feasibility algorithm would solve BDD1/(4n2), while Theorem B gives average-case hardness for an efficiently samplable polytope distribution under decision-LWE hardness.

    Source: §1 · p. 3

  • Takeaways & Limitations

    These constructions satisfy the rank-one promise, but finding the relevant basis is as hard as BDD or decision-LWE for the respective instances.

    Source: §1 · p. 4

    The negative results are conditional: Theorem A relies on classical lattice hardness, while Theorem B relies on quantum hardness.

    Source: §1 · p. 3

Abstract

from arXiv · show

A rational polyhedron has Chv\'atal rank at most one if a single round of Chv\'atal-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\'atal 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.

1 Introduction

The paper answers the open polynomial-time question for integer feasibility under the promise P′ = PI negatively, conditional on lattice-hardness assumptions. Its reductions use polytopes with width below one along the rows of a suitable unimodular matrix, although finding such a matrix is hard.

1 Introduction

  • The question concerns a promise problem: integer feasibility is in NP ∩ coNP under P′ = PI, and whether it is polynomial-time decidable has remained open.Without the promise, deciding whether P′ is empty is NP-complete.Source: §1 · p. 2
  • A polynomial-time algorithm for integer feasibility under P′ = PI would solve BDD1/(4n2), and would also yield algorithms for uSVP4n2 and randomized GapSVP with γ = 4n5/2/√log n.The BDD reduction preserves dimension; the further consequences use reductions of Lyubashevsky and Micciancio.Source: §1 · p. 3
  • Theorem B gives an efficiently samplable distribution of polytopes with P′ = PI with high probability, on which successful randomized feasibility algorithms would solve decision-LWE.The constraints are integral with coefficients bounded by a polynomial in the dimension.Source: §1 · p. 3
  • Theorem A is worst-case, whereas Theorem B gives average-case hardness; their reductions rely on different conjectures and have different dimension behavior.Theorem A relies on classical lattice hardness and preserves dimension; Theorem B relies on quantum hardness and increases dimension from n to O(n log n).Source: §1 · p. 3
  • If a polyhedron has width less than one along every row of a unimodular matrix, then P′ = PI, and the integer hull needs at most 2n CG cuts.For lattice parallelepipeds, the relevant rows arise from a basis of the dual lattice; the width bound holds when r < λ1(L)/(2n2).Source: §1 · pp. 3–4
  • For Theorem A, trying power-of-two radii and binary-search queries reduces BDD to feasibility queries on rational subpolyhedra that retain the promise.Source: §1 · p. 4
  • For Theorem B, one parallelepiped distinguishes LWE targets from uniform targets: it contains an integer point in the LWE case and none with high probability in the uniform case.Source: §1 · p. 4
  • A short dual basis makes these instances easy to solve, but finding such a basis is as hard as BDD or decision-LWE for the respective constructions.With the basis, Babai’s algorithm finds a feasible point, or a short CG refutation can be given.Source: §1 · p. 4

2 Preliminaries

The preliminaries establish notation for polyhedra, lattices, and promise problems, then specify the LWE and lattice problems used in the paper. They also explain why restricting to rank exactly one suffices for the results.

2 Preliminaries

  • For a polyhedron P, widthP(c) is the sum of its maximum values in directions c and −c; a rational subpolyhedron is a rational polyhedron contained in P.Source: §2 · p. 5
  • A lattice is L = BZn; its dual is L∗ = B−TZn, and dist(t, L) is the minimum Euclidean distance from t to a lattice vector.Source: §2 · p. 5
  • A promise-problem algorithm must run within its time bound on every input and answer correctly on promised inputs; a reduction may use an oracle for the target promise problem.A reduction preserves dimension when all queries on an n-dimensional input have dimension n.Source: §2 · p. 5
  • The preliminaries define BDD, uSVP, GapSVP, and SIVP through their lattice-distance, shortest-vector, gap-decision, and independent-vector tasks.Source: §2 · p. 5
  • Decision-LWE distinguishes an LWE sample from a uniform instance, where t ≡ ATs + e (mod q) and the error entries are independently drawn from χ.The stated success criterion requires the output probabilities on the two instance types to differ by at least n−c for some constant c > 0.Source: §2 · p. 5
  • It suffices to consider polytopes of Chvátal rank exactly one because rank-zero instances can be processed first, leaving either a known answer or a rank-one instance.Source: §2 · pp. 5–6

3 A sufficient condition for Chv´atal rank at most one

A polyhedron with width less than one along every row of a unimodular matrix has Chvátal rank at most one. The strict bound also yields a short CG-cut description and constrains the integer points it can contain.

3 A sufficient condition for Chv´atal rank at most one

  • Width below one along each row of a unimodular matrix guarantees P′ = PI, with PI obtainable using at most 2n CG cuts.Such a polyhedron contains at most one integer point, and every rational subpolyhedron also has Chvátal rank at most one.Source: §3 · p. 6
  • The 2n cuts in the unimodular directions pin each coordinate to an integer, leaving either no point or a single integer point.Unimodularity ensures that the point determined by those integer coordinates is itself integral.Source: §3 · p. 6
  • The strict width bound cannot be relaxed to one: the cropped cube has width one along every coordinate direction and Chvátal rank at least n.Moreover, an integral polyhedron need not pass the same rank-one guarantee to its rational subpolyhedra: [0, 1]^n contains a cropped cube of rank at least n.Source: §3 · p. 6

4 Parallelepipeds defined by lattices

Lattice-based parallelepipeds have unimodular width directions derived from dual-lattice bases. When the radius is sufficiently small, the width condition guarantees rank at most one for the parallelepiped and all its rational subpolyhedra.

4 Parallelepipeds defined by lattices

  • The illustrated example has widths 15/16 and 3/4 along dual-basis rows, versus 39/16 and 27/16 along e1 and e2.The parallelepiped’s only integer point maps to the sole lattice vector in the target square.Source: §4 · p. 7
  • Every dual-lattice basis gives unimodular width directions BTw_i, with width 2r∥w_i∥_1 along each corresponding row.Every unimodular matrix arises from a dual-lattice basis in this way.Source: §4 · p. 7
  • A dual-lattice basis exists with each ∥w_i∥_1 ≤ n^2/λ1(L), making all those widths less than one below the stated radius threshold.The basis bound follows using a transference theorem and a basis bound in terms of successive minima.Source: §4 · p. 7
  • For r < λ1(L)/(2n^2), Q(B,t,r) and every rational subpolyhedron have Chvátal rank at most one, and Q contains at most one integer point.The integer points of Q correspond to lattice vectors within ℓ∞-distance r of t.Source: §4 · pp. 6–7

5 Hardness from worst-case lattice problems

The paper reduces bounded distance decoding to integer feasibility on rational subpolyhedra that satisfy the rank-one promise. This yields worst-case lattice-problem consequences, while short refutations for these polytopes remain hard to find.

5 Hardness from worst-case lattice problems

  • A deterministic polynomial-time oracle for promised integer feasibility solves BDD1/(4n^2) using queries that are rational subpolyhedra of thin lattice parallelepipeds.Each query is a polytope in R^n described by at most 2n + 1 rational inequalities.Source: §5 · p. 8
  • The reduction guesses a radius by trying powers of two, then uses coordinate-wise binary search to recover the closest lattice vector.For a suitable radius, the parallelepiped has the closest vector’s preimage as its unique integer point; queries are made in increasing radius order.Source: §5 · p. 8
  • A polynomial-time promised-feasibility algorithm would also solve uSVP4n^2 deterministically and GapSVP with γ = 4n^(5/2)/√log n randomly.The corollary also transfers subexponential running times, and randomized feasibility algorithms yield randomized versions of the lattice algorithms.Source: §5 · p. 9
  • The relevant refutations use at most 2n + 1 CG cuts, but finding a refutation or a width-certifying unimodular matrix is as hard as BDD1/(4n^2).Thus, for these polytopes, the difficulty lies in finding the refutations rather than their size.Source: §5 · pp. 9–10

6 Hardness from learning with errors

The section reduces decision-LWE to integer feasibility on parallelepipeds that satisfy the rank-at-most-one promise with high probability. It establishes average-case hardness for an efficiently samplable distribution and derives worst-case and quantum lattice-problem consequences.

Promise guarantee

  • For uniformly random A, λ1(Λq(AT)) > q/8 with probability at least 1 − q^n2^-m, providing the lattice-length bound used to establish the promise.The promise follows when the chosen radius satisfies r < λ1(Λq(AT))/(2m^2).Source: §6 · p. 10

Proposition 12

  • When r < λ1(Λq(AT))/(2m^2), every rational subpolyhedron of Q has Chvátal rank at most one; Q contains an integer point with probability at least 1 − εχ on LWE instances and at most 2^-m on uniform instances.The reduction uses this difference in integer feasibility to distinguish the two instance types.Source: §6 · p. 11

Construction

  • The parallelepiped Q is constructed from a polynomial-time computable basis B of Λq(AT), with integral data and 2m inequalities.Its defining inequalities are Bx ≤ t + r1 and −Bx ≤ −t + r1.Source: §6 · p. 11

Theorem 13

  • For χ = Ψ̄α and the stated parameters, Theorem 13 yields an explicit, polynomial-time samplable distribution of hard instances.The Gaussian error distribution is lifted from Zq to Z and can be sampled efficiently.Source: §6 · p. 11
  • A randomized polynomial-time algorithm correct with probability at least 1/2 + n^-c over the efficiently sampled distribution D would solve decision-LWE with m samples.A sample from D has Chvátal rank at most one with probability at least 1 − 2^-2nk.Source: §6 · p. 11

Worst-case consequence

  • An algorithm correct with probability 2/3 on every specified parallelepiped would meet Theorem 13’s average-case success condition, extending the consequence to worst-case promised feasibility.The cited guarantee applies to rational polytopes with P′ = PI.Source: §6 · p. 12

Quantum consequences

  • A randomized polynomial-time algorithm as in Theorem 13 would yield a polynomial-time quantum algorithm for GapSVPγ and SIVPγ with γ = Õ(n^3).This follows by combining the LWE reduction with Regev’s result [33].Source: §6 · p. 12
Loading 2610.10911v1…