pith. sign in

arxiv: 2604.04851 · v1 · submitted 2026-04-06 · 🧮 math.OC

Curvature batching gives single-exponential integer quadratic programming

Cinar Ari , Robert Hildebrand This is my paper

Pith reviewed 2026-05-10 19:11 UTC · model grok-4.3

classification 🧮 math.OC
keywords integer quadratic programmingsingle-exponential algorithmfixed-parameter tractabilitycurvature batchinginteger linear programmingindefinite quadratic formscombinatorial optimization
0
0 comments X

The pith

Integer quadratic programming admits a single-exponential algorithm via curvature-based constraint batching.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes the first single-exponential algorithm for general integer quadratic programming parameterized by dimension n and maximum coefficient size L. Earlier results proved fixed-parameter tractability for this problem but left the dependence on n super-exponential. The method classifies directions in the kernel of the quadratic form according to the sign of the curvature they produce. When no negative-curvature direction remains, every relevant gradient constraint can be added in one batch, replacing the previous chain of determinant-squaring steps with a single polynomial blow-up before the problem reduces to an ordinary integer linear program. The same technique supplies explicit complexity bounds for several related FPT problems and for concave integer minimization whose running time depends only on the constraint matrix.

Core claim

We give the first single-exponential algorithm for IQP, solving it in time (n L_A^n Δ(A) L_Q)^{O(n)} · poly(φ), which is (nL)^{O(n^2)} · poly(φ) in general. This bound is obtained by curvature batching: kernel directions are classified by the sign of their quadratic curvature, and when no negative-curvature direction exists all gradient constraints are imposed simultaneously in a single batch. The resulting inflated instance is then an ordinary integer linear program.

What carries the argument

Curvature batching: the classification of kernel directions of the quadratic form by the sign of their curvature, which permits all gradient constraints to be imposed simultaneously in one step whenever no negative curvature is present.

If this is right

  • General IQP instances can be solved in time (nL)^{O(n^2)} poly(φ).
  • Instances whose constraint matrix is totally unimodular admit strictly better running times.
  • Concave integer minimization over a polytope {Ax ≤ b} ∩ Z^n has parametric complexity depending only on A, independent of b.
  • Explicit complexity bounds are obtained for a number of other FPT algorithms and optimization problems.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The single-batch reduction to ILP suggests that further gains for indefinite quadratics may come from improved ILP algorithms under the same parameterization.
  • If curvature batching can be adapted to other indefinite quadratic objectives arising in combinatorial problems, additional tasks could enter single-exponential FPT.
  • Empirical testing on graph-quadratic instances could reveal whether the theoretical exponent is close to tight in practice.

Load-bearing premise

Kernel directions of the quadratic form can be classified by the sign of their curvature, and the absence of negative-curvature directions allows all gradient constraints to be imposed simultaneously without losing correctness or increasing the exponent.

What would settle it

An IQP instance on which the curvature classification either produces an incorrect optimum or forces the running time to exceed the stated single-exponential bound after the batching step.

Figures

Figures reproduced from arXiv: 2604.04851 by Cinar Ari, Robert Hildebrand.

Figure 1
Figure 1. Figure 1: Visual representation of branches This idea can be made algorithmic. Lokshtanov’s algorithm is recursively solving lower dimen￾sional problems by iteratively adding new equalities to the original problem. At each node, there is an equality system Cx = d where the kernel of C represents precisely the set of directions one can move in and remain feasible with respect to Cx = d. First, the algorithm finds an … view at source ↗
Figure 2
Figure 2. Figure 2: Batch branching [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
read the original abstract

Integer Quadratic Programming (IQP), $\min\{x^T Q x + c^T x : Ax \le b,\, x\in\Z^n\}$, is a fundamental problem in combinatorial optimization. While the convex and concave special cases admit polynomial-time algorithms for fixed~$n$, the general indefinite case is considerably harder: it was only recently shown to lie in NP, and the FPT algorithm, due to Lokshtanov, establishes fixed-parameter tractability parameterized by $n$ and the largest coefficient~$L$ without giving an explicit running time. We give the first single-exponential algorithm for IQP, solving it in time $ \bigl(n\,L^n_A\,\Delta(A)\,L_Q\bigr)^{O(n)}\cdot\mathrm{poly}(\varphi), $ which is $(nL)^{O(n^2)}\cdot\mathrm{poly}(\varphi)$ in general using the same parameterization. We achieve improvements for structured cases like total unimodularity and further state explicit complexity results for a number of FPT algorithms and optimization problems. The single-exponential bound is achieved via curvature batching: we classify kernel directions by the sign of their quadratic curvature and observe that when no negative-curvature direction exists, all gradient constraints can be imposed simultaneously in a single batch. This replaces the chain of determinant squarings inherent in sequential branching with a single polynomial inflation, after which the remaining problem is an ILP. As a secondary contribution, we give an explicit bound for concave integer minimization over a polytope $\{Ax \le b\} \cap \Z^n$ whose parametric complexity depends only on the constraint matrix~$A$ and is independent of the right-hand side~$b$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 4 minor

Summary. The paper claims to give the first single-exponential algorithm for general Integer Quadratic Programming (IQP), min{x^T Q x + c^T x : A x ≤ b, x ∈ Z^n}, running in time (n L_A^n Δ(A) L_Q)^{O(n)} · poly(φ) (equivalently (n L)^{O(n^2)} · poly(φ) in the worst case). The algorithm proceeds by classifying kernel directions of the quadratic form according to the sign of their curvature; when no negative-curvature direction exists, all gradient constraints are imposed simultaneously in a single batch, after which the problem reduces to an ILP via a polynomial-size inflation. A secondary result gives an explicit FPT bound for concave integer minimization over {A x ≤ b} ∩ Z^n whose complexity depends only on A and is independent of b. Explicit bounds are also stated for several structured cases including total unimodularity.

Significance. If the central claim holds, the result is a notable advance: it supplies the first explicit single-exponential FPT algorithm for indefinite IQP (improving on the prior FPT result of Lokshtanov that lacked an explicit single-exponential bound) and replaces sequential determinant-squaring chains with a single polynomial inflation. The curvature-batching technique and the A-only parametric bound for concave minimization are technically interesting and may apply to other indefinite quadratic or non-convex integer programs. The paper also supplies concrete complexity statements for several related FPT problems.

minor comments (4)
  1. The abstract and introduction should explicitly define the parameters L_A, Δ(A), L_Q and φ at first use and state the precise parameterization under which the single-exponential bound holds.
  2. Section 4 (or wherever the curvature-batching procedure is formalized) should include a short table or pseudocode box summarizing the classification of kernel directions and the batching step, to improve readability.
  3. The secondary result on concave minimization should be stated as a numbered theorem with its exact running time, rather than only described in prose.
  4. A few sentences comparing the new bound with the best previous explicit FPT bounds (even if worse than single-exponential) would help readers assess the improvement.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment and recommendation of minor revision. The referee's summary accurately reflects the paper's contributions: the first explicit single-exponential FPT algorithm for indefinite IQP via curvature batching, the replacement of sequential determinant-squaring with a single polynomial inflation, and the A-only parametric bound for concave minimization. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper constructs an explicit single-exponential algorithm for indefinite IQP by introducing curvature batching: kernel directions of the quadratic form are classified by the sign of their curvature, and in the absence of negative-curvature directions all gradient constraints are imposed simultaneously before reduction to an ILP. This replaces sequential determinant-squaring chains with a single polynomial inflation. The approach relies on a new classification technique rather than any fitted parameter, self-citation chain, or redefinition of the target bound. External citations (e.g., Lokshtanov for prior FPT membership) are independent and do not bear the single-exponential claim. The secondary result on concave minimization is likewise parameterized solely by the constraint matrix A. No step reduces by construction to its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The claim rests on standard results about ILP solvability in fixed dimension and the correctness of curvature-based classification of kernel directions; no free parameters or invented entities with independent evidence are stated in the abstract.

axioms (1)
  • standard math Integer linear programming in fixed dimension is solvable in polynomial time (or single-exponential in the parameterization used).
    The final step after curvature batching reduces to an ILP whose complexity is invoked to obtain the overall bound.
invented entities (1)
  • curvature batching no independent evidence
    purpose: Classify kernel directions by quadratic curvature sign to enable simultaneous constraint imposition and avoid repeated determinant squaring.
    New algorithmic technique introduced to achieve the single-exponential bound.

pith-pipeline@v0.9.0 · 5606 in / 1270 out tokens · 53437 ms · 2026-05-10T19:11:36.207843+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

  • IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear
    ?
    unclear

    Relation between the paper passage and the cited Recognition theorem.

    classify kernel directions by the sign of their quadratic curvature and observe that when no negative-curvature direction exists, all gradient constraints can be imposed simultaneously in a single batch. This replaces the chain of determinant squarings ... after which the remaining problem is an ILP.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages

  1. [1]

    Agrell, T

    E. Agrell, T. Eriksson, A. Vardy, and K. Zeger, Closest point search in lattices,IEEE Trans. Inform. Theory48 (2002) 2201–2214

    work page 2002

  2. [2]

    R. K. Ahuja, D. S. Hochbaum, and J. B. Orlin, Solving the convex cost integer dual network flow problem,Management Sci.49 (2003) 950–964

    work page 2003

  3. [3]

    Atamt¨ urk and D

    A. Atamt¨ urk and D. S. Hochbaum, Capacity acquisition, subcontracting, and lot sizing,Man- agement Sci.47 (2001) 1081–1100

    work page 2001

  4. [4]

    Aute and F

    S. Aute and F. Panolan, Parameterized algorithms for minimum sum vertex cover, in:Proc. LATIN 2024, LNCS 14579, Springer, 2024, pp. 179–193. 20

    work page 2024

  5. [5]

    W. Cook, A. M. H. Gerards, A. Schrijver, and ´E. Tardos, Sensitivity theorems in integer linear programming,Math. Programming34 (1986) 251–264

    work page 1986

  6. [6]

    W. Cook, M. Hartmann, R. Kannan, and C. McDiarmid, On integer points in polyhedra, Combinatorica12 (1992) 27–37

    work page 1992

  7. [7]

    Dadush,Integer programming, lattice algorithms, and deterministic volume estimation, Ph.D

    D. Dadush,Integer programming, lattice algorithms, and deterministic volume estimation, Ph.D. thesis, Georgia Institute of Technology, 2012

    work page 2012

  8. [8]

    Del Pia, S

    A. Del Pia, S. S. Dey, and M. Molinaro, Mixed-integer quadratic programming is in NP,Math. Programming162 (2017) 225–240

    work page 2017

  9. [9]

    Del Pia and R

    A. Del Pia and R. Weismantel, Integer quadratic programming in the plane, in:Proc. 25th ACM-SIAM SODA, 2014, pp. 840–846

    work page 2014

  10. [10]

    Eiben, R

    E. Eiben, R. Ganian, D. Knop, and S. Ordyniak, Solving integer quadratic programming via explicit and structural restrictions, in:Proc. AAAI-19, 2019, pp. 1477–1484

    work page 2019

  11. [11]

    M. R. Garey and D. S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979

    work page 1979

  12. [12]

    G. H. Golub and C. F. Van Loan,Matrix Computations, 4th ed., Johns Hopkins University Press, 2013

    work page 2013

  13. [13]

    Granot and J

    F. Granot and J. Skorin-Kapov, Some proximity and sensitivity results in quadratic integer programming,Math. Programming47 (1990) 259–268

    work page 1990

  14. [14]

    Gu´ eret, C

    C. Gu´ eret, C. Prins, and M. Sevaux,Applications of Optimization with Xpress-MP, Dash Optimization, 2002

    work page 2002

  15. [15]

    M. E. Hartmann, Cutting planes and the complexity of the integer hull, Ph.D. thesis, Cornell University, Ithaca, NY, 1989

    work page 1989

  16. [16]

    Heinz, Complexity of integer quasiconvex polynomial optimization,J

    S. Heinz, Complexity of integer quasiconvex polynomial optimization,J. Complexity21 (2005) 543–556

    work page 2005

  17. [17]

    Hildebrand and M

    R. Hildebrand and M. K¨ oppe, A new Lenstra-type algorithm for quasiconvex polynomial integer minimization with complexity 2 O(nlogn) ,Discrete Optim.10 (2013) 69–83

    work page 2013

  18. [18]

    Hlinˇ en´ y and A

    P. Hlinˇ en´ y and A. Sankaran, Exact crossing number parameterized by vertex cover, in:Proc. GD 2019, LNCS 11904, Springer, 2019, pp. 307–319

    work page 2019

  19. [19]

    Kannan, Minkowski’s convex body theorem and integer programming,Math

    R. Kannan, Minkowski’s convex body theorem and integer programming,Math. Oper. Res.12 (1987) 415–440

    work page 1987

  20. [20]

    L. G. Khachiyan, Polynomial algorithms in linear programming,USSR Comput. Math. and Math. Phys.20 (1980) 53–72

    work page 1980

  21. [21]

    Khachiyan and L

    L. Khachiyan and L. Porkolab, Integer optimization on convex semialgebraic sets,Discrete Comput. Geom.23 (2000) 207–224

    work page 2000

  22. [22]

    Koana, C

    T. Koana, C. Komusiewicz, A. Nichterlein, and F. Sommer, Computing densestk-subgraph with structural parameters,J. Combin. Optim.45 (2023) 17. 21

    work page 2023

  23. [23]

    K¨ oppe, On the complexity of nonlinear mixed-integer optimization, in:Mixed Integer Nonlinear Programming, Springer, 2012, pp

    M. K¨ oppe, On the complexity of nonlinear mixed-integer optimization, in:Mixed Integer Nonlinear Programming, Springer, 2012, pp. 533–557

    work page 2012

  24. [24]

    D. C. Lay,Linear Algebra and its Applications, Addison-Wesley, 2000

    work page 2000

  25. [25]

    H. W. Lenstra Jr., Integer programming with a fixed number of variables,Math. Oper. Res.8 (1983) 538–548

    work page 1983

  26. [26]

    Lokshtanov, Parameterized integer quadratic programming: Variables and coefficients, arXiv:1511.00310v2, 2017

    D. Lokshtanov, Parameterized integer quadratic programming: Variables and coefficients, arXiv:1511.00310v2, 2017

    work page arXiv 2017

  27. [27]

    Minoux, Solving integer minimum cost flows with separable convex cost objective polyno- mially,Math

    M. Minoux, Solving integer minimum cost flows with separable convex cost objective polyno- mially,Math. Programming Study26 (1986) 237–239

    work page 1986

  28. [28]

    Pochet and L

    Y. Pochet and L. A. Wolsey,Production Planning by Mixed Integer Programming, Springer, 2006

    work page 2006

  29. [29]

    Reis and T

    V. Reis and T. Rothvoss, The subspace flatness conjecture and faster integer programming, in:Proc. 64th IEEE FOCS, 2023, pp. 974–988

    work page 2023

  30. [30]

    Schrijver,Theory of Linear and Integer Programming, Wiley, 1986

    A. Schrijver,Theory of Linear and Integer Programming, Wiley, 1986

    work page 1986

  31. [31]

    Zemmer,Integer polynomial optimization in fixed dimension, Ph.D

    K. Zemmer,Integer polynomial optimization in fixed dimension, Ph.D. thesis, ETH Z¨ urich, 2017. 22

    work page 2017