  We study an important case of ILPs $\max\{c^Tx \ \vert\ \mathcal Ax = b, l
\leq x \leq u,\, x \in \mathbb{Z}^{n t} \} $ with $n\cdot t$ variables and
lower and upper bounds $\ell, u\in\mathbb Z^{nt}$. In $n$-fold ILPs non-zero
entries only appear in the first $r$ rows of the matrix $\mathcal A$ and in
small blocks of size $s\times t$ along the diagonal underneath. Despite this
restriction many optimization problems can be expressed in this form. It is
known that $n$-fold ILPs can be solved in FPT time regarding the parameters $s,
r,$ and $\Delta$, where $\Delta$ is the greatest absolute value of an entry in
$\mathcal A$. The state-of-the-art technique is a local search algorithm that
subsequently moves in an improving direction. Both, the number of iterations
and the search for such an improving direction take time $\Omega(n)$, leading
to a quadratic running time in $n$. We introduce a technique based on Color
Coding, which allows us to compute these improving directions in logarithmic
time after a single initialization step. This leads to the first algorithm for
$n$-fold ILPs with a running time that is near-linear in the number $nt$ of
variables, namely $(rs\Delta)^{O(r^2s + s^2)} L^2 \cdot nt \log^{O(1)}(nt)$,
where $L$ is the encoding length of the largest integer in the input. In
contrast to the algorithms in recent literature, we do not need to solve the LP
relaxation in order to handle unbounded variables. Instead, we give a
structural lemma to introduce appropriate bounds. If, on the other hand, we are
given such an LP solution, the running time can be decreased by a factor of
$L$.
