Delta-modular ILP Problems of Bounded Co-dimension, Discrepancy, and Convolution

For k, n ≥ 0, and c ∈ Zⁿ, we consider ILP problems {gather*} max\{ c^ x A x = b,\, x ∈ Z^n≥ 0 \} with A ∈ Zk × n, $rank(A) = k$, b ∈ Zᵏ and max\{ c^ x A x ≤ b,\, x ∈ Z^n \} with A ∈ Z(n+k) × n, $rank(A) = n$, b ∈ Zⁿ⁺ᵏ. {gather*} The first problem is called an ILP problem in the standard form of the codimension k, and the second problem is called an ILP problem in the canonical form with $n+k$ constraints. We show that, for any sufficiently large Δ, both problems can be solved with 2O(k) · (fk,d · Δ)² / 2^Ω(√log(fk,d · Δ)) operations, where fk,d = min \ kk/2, (log k · log (d + k))k/2 \, d is the dimension of a corresponding polyhedron and Δ is the maximum absolute value of rank(A) × rank(A) sub-determinants of A. As our second main result, we show that the feasibility variants of both problems can be solved with 2O(k) · fk,d · Δ · log³(fk,d · Δ) operations. The constant fk,d can be replaced by other constant gk,Δ = (log k · log (k Δ))k/2 that depends only on k and Δ. Additionally, we consider different partial cases with $k=0$ and $k=1$, which have interesting applications. As a result of independent interest, we propose an n²/2Ω(√log n)-time algorithm for the tropical convolution problem on sequences, indexed by elements of a finite Abelian group of the order n. This result is obtained, reducing the above problem to the matrix multiplication problem on a tropical semiring and using seminal algorithm by R. Williams.