  N-fold integer programming is a fundamental problem with a variety of natural
applications in operations research and statistics. Moreover, it is universal
and provides a new, variable-dimension, parametrization of all of integer
programming. The fastest algorithm for $n$-fold integer programming predating
the present article runs in time $O(n^{g(A)}L)$ with $L$ the binary length of
the numerical part of the input and $g(A)$ the so-called Graver complexity of
the bimatrix $A$ defining the system. In this article we provide a drastic
improvement and establish an algorithm which runs in time $O(n^3 L)$ having
cubic dependency on $n$ regardless of the bimatrix $A$. Our algorithm can be
extended to separable convex piecewise affine objectives as well, and also to
systems defined by bimatrices with variable entries. Moreover, it can be used
to define a hierarchy of approximations for any integer programming problem.
