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

For k, n 0, and c Zⁿ, we consider ILP problems gather* \ c^ x A x = b, \, x Zⁿ ₀ \ with A Z^k n, rank (A) = k, b Z^{k and} \ c^ x A x b, \, x Zⁿ \ with A Z^ (n+k) n, rank (A) = n, b Z^{n+k. } 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 2^O (k) (f₊, ₃) ² / 2^ ( (f₊, ₃) ) operations, where f₊, ₃ = \ k^{k/2, (k (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 2^O (k) f₊, ₃ ³ (f₊, ₃) operations. The constant f₊, ₃ can be replaced by other constant g₊, = (k (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^ (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.