Seminars
View all Seminars | Download ICal for this eventThe Subspace Flatness Conjecture and Faster Integer Programming
Series: Bangalore Theory Seminars
Speaker: Victor Reis University of Washington
Date/Time: Jun 23 11:00:00
Location: Online Talk (See Teams link below)
Abstract:
In a seminal paper, Kannan and Lovasz (1988) considered a quantity μKL(? , K) which denotes the best volume-based lower bound on the covering radius μ(? , K) of a convex body K with respect to a lattice ? . Kannan and Lovasz proved that μ(? , K) ? n. μKL(? , 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 Lovasz. We settle this conjecture up to a constant in the exponent by proving that μ(? , K) ? O(log3(n)).μKL(? , 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 log4(n)).
Joint work with Thomas Rothvoss.
Microsoft Teams link:
Link
We are grateful to the Kirani family for generously supporting the theory seminar series
Hosts: Rachana Gusain, Rahul Madhavan, Rameesh Paul, KVN Sreenivas