Delta-modular ILP Problems of Bounded Codimension, Discrepancy, and Convolution (new version)

For integers $k,n\ge 0$ and a cost vector $c\in Z^n$, we study two fundamental integer linear programming (ILP) problems: $$\text{(Standard Form)}\max \{c^{\mathrm{\top }}x\text{\hspace{0.17em}⁣}:Ax=b,x\in Z_{\ge 0}^n\}\text{ with }A\in Z^{k\times n},\text{rank}(A)=k,b\in Z^k,$$ $$\text{(Canonical Form)}\max \{c^{\mathrm{\top }}x\text{\hspace{0.17em}⁣}:Ax\le b,x\in Z^n\}\text{ with }A\in Z^{(n+k)\times n},\text{rank}(A)=n,b\in Z^{n+k}\mathrm{.}$$ We present improved algorithms for both problems and their feasibility versions, parameterized by $k$ and $\mathrm{\Delta }$, where $\mathrm{\Delta }$ denotes the maximum absolute value of $\text{rank}(A)\times \text{rank}(A)$ subdeterminants of $A$. Our main complexity results, stated in terms of required arithmetic operations, are: $$\text{Optimization:}O(\log k{)}^{2k}\cdot {\mathrm{\Delta }}^2\mathrm{/}{2}^{\mathrm{\Omega }(\sqrt{\log \mathrm{\Delta }})}+2^{O(k)}\cdot \text{poly}(\phi ),$$ $$\text{Feasibility:}O(\log k{)}^k\cdot \mathrm{\Delta }\cdot (\log \mathrm{\Delta }{)}^3+2^{O(k)}\cdot \text{poly}(\phi ),$$ where $\phi$ represents the input size measured by the bit-encoding length of $(A,b,c)$. We also examine several special cases when $k\in \{0,1\}$, which have important applications in: expected computational complexity of ILP with varying right-hand side $b$, ILP problems with generic constraint matrices, ILP problems on simplices. Our results yield improved complexity bounds for these specific scenarios. As independent contributions, we present: An $n^2\mathrm{/}{2}^{\mathrm{\Omega }(\sqrt{\log n})}$-time algorithm for the tropical convolution problem on sequences indexed by elements of a finite Abelian group of order $n$; A complete and self-contained error analysis of the generalized DFT over Abelian groups in the Word-RAM model.