Convex Minimization with Integer Minima in widetilde O(n4) Time

Given a convex function f on ℝn with an integer minimizer, we show how to find an exact minimizer of f using O(n2 log n) calls to a separation oracle and O(n4 log n) time. The previous best polynomial time algorithm for this problem given in [Jiang, SODA 2021, JACM 2022] achieves O(n2loglog n/log n) oracle complexity. However, the overall runtime of Jiang's algorithm is at least widetildeOmega(n8), due to expensive sub-routines such as the Lenstra-Lenstra-Lov'asz (LLL) algorithm [Lenstra, Lenstra, Lov'asz, Math. Ann. 1982] and random walk based cutting plane method [Bertsimas, Vempala, JACM 2004]. Our significant speedup is obtained by a nontrivial combination of a faster version of the LLL algorithm due to [Neumaier, Stehl'e, ISSAC 2016] that gives similar guarantees, the volumetric center cutting plane method (CPM) by [Vaidya, FOCS 1989] and its fast implementation given in [Jiang, Lee, Song, Wong, STOC 2020]. For the special case of submodular function minimization (SFM), our result implies a strongly polynomial time algorithm for this problem using O(n3 log n) calls to an evaluation oracle and O(n4 log n) additional arithmetic operations. Both the oracle complexity and the number of arithmetic operations of our more general algorithm are better than the previous best-known runtime algorithms for this specific problem given in [Lee, Sidford, Wong, FOCS 2015] and [Dadush, V'egh, Zambelli, SODA 2018, MOR 2021].