***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Victor Reis (IAS)

Thursday 22nd February, 3:00 in Fine Hall 224.

Title: The subspace flatness conjecture and faster integer programming

In a seminal paper, Kannan and Lovász (1988) considered a quantity
mu_{KL} (L,K) which denotes the best volume-based lower bound on the
covering radius mu(L,K) of a convex body K with respect to a lattice L.
Kannan and Lovász proved that mu(L,K) \leq n \cdot mu_{KL}(L,K), and the
Subspace Flatness Conjecture by Dadush (2012) claims a O(log n) factor
suffices, which would match the lower bound from the work of Kannan and
Lovász.

We settle this conjecture up to a constant in the exponent by proving that
mu(L,K) \leq O(log^3(n)) \cdot mu_{KL} (L,K). Our proof is based on the
Reverse Minkowski Theorem due to Regev and Stephens-Davidowitz (2017).
Following the work of Dadush (2012, 2019), we obtain a (log n)^{4n}-time
randomized algorithm to solve integer programs in n variables. Another
implication of our main result is a near-optimal flatness constant of O(n
log^3(n)). Joint work with Thomas Rothvoss.


		----------------------------------


Anyone wishing to be added to or removed from the mailing list should
contact Paul Seymour (pds@math.princeton.edu)