A Simple Algorithm for Counting Solutions to Integer Programs

We consider the problem of counting solutions to integer linear programming problems of the form $\{x\in {\mathbb{Z}}_{\ge 0}^n:Ax=b\}$ where $A\in \{-\mathrm{\Delta },\dots ,\mathrm{\Delta }{\}}^{m\times n}$ and $b\in {\mathbb{Z}}^m$. We present an algorithm that counts solutions with $(n\mathrm{\Delta }{)}^{m+o(1)}\text{\hspace{0.17em}⁣}\cdot \log \parallel b\parallel$ arithmetic operations. This simplifies the algorithm of Gribanov and Malyshev, who considered the problem for the more general setting in which $A$ is $\mathrm{\Delta }$-modular.