- The Subspace Flatness Conje...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in February 2024

## 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:**

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