Advances on Strictly $Δ$-Modular IPs

There has been significant work recently on integer programs (IPs) $\min\{c^\top x \colon Ax\leq b,\,x\in \mathbb{Z}^n\}$ with a constraint marix $A$ with bounded subdeterminants. This is motivated by a well-known conjecture claiming that, for any constant $Δ\in \mathbb{Z}_{>0}$, $Δ$-modular IPs are efficiently solvable, which are IPs where the constraint matrix $A\in \mathbb{Z}^{m\times n}$ has full column rank and all $n\times n$ minors of $A$ are within $\{-Δ, \dots, Δ\}$. Previous progress on this question, in particular for $Δ=2$, relies on algorithms that solve an important special case, namely strictly $Δ$-modular IPs, which further restrict the $n\times n$ minors of $A$ to be within $\{-Δ, 0, Δ\}$. Even for $Δ=2$, such problems include well-known combinatorial optimization problems like the minimum odd/even cut problem. The conjecture remains open even for strictly $Δ$-modular IPs. Prior advances were restricted to prime $Δ$, which allows for employing strong number-theoretic results. In this work, we make first progress beyond the prime case by presenting techniques not relying on such strong number-theoretic prime results. In particular, our approach implies that there is a randomized algorithm to check feasibility of strictly $Δ$-modular IPs in strongly polynomial time if $Δ\leq4$.