The Subspace Flatness Conjecture and Faster Integer Programming

Speaker: Thomas Rothvoss

Date: Tuesday, February 20, 2024

Time: 4:15 PM to 5:15 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-G449

Event Type: Seminar

Room Description: Refreshments at 4:00pm

Host: Michael Goemans, MIT

Contact: Joanne Talbot Hanley, 617-253-6054, joanne@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, theory-seminars@csail.mit.edu

Reminder Subject: TALK: TOC Seminar: The Subspace Flatness Conjecture and Faster Integer Programming by Thomas Rothvoss, Tuesday, February 20 at 4:15 (Refreshments at 4:00pm) in 32-G449

Abstract (in latex):
In a seminal paper, Kannan and Lov\'asz (1988) considered a quantity $\mu_{KL}(\Lambda,K)$
which denotes the best volume-based lower bound on the \emph{covering radius} $\mu(\Lambda,K)$ of a convex
body $K$ with respect to a lattice $\Lambda$. Kannan and Lov\'asz proved that $\mu(\Lambda,K) \leq n \cdot \mu_{KL}(\Lambda,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\'asz.
We settle this conjecture up to a constant in the exponent by proving that $\mu(\Lambda,K) \leq O(\log^{3}(n)) \cdot \mu_{KL} (\Lambda,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)^{O(n)}$-time randomized algorithm to
solve integer programs in $n$ variables.
Another implication of our main result is a near-optimal \emph{flatness constant} of $O(n \log^{3}(n))$.

This is joint work with Victor Reis.

Research Areas:

Impact Areas:

See other events that are part of the Theory of Computation (ToC) Seminar 2024.

Created by Joanne Talbot Hanley Email at Wednesday, February 07, 2024 at 2:02 PM.