BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20230623T120000Z
UID:7e5e1e2c7f363fe9b9702bc9afc7b698-472
DTSTAMP:19700101T120011Z
DESCRIPTION:The Subspace Flatness Conjecture and Faster Integer Programming
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/472/the-subspace-flatness-conjecture-and-faster-integer-programming/
SUMMARY: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:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d


We are grateful to the Kirani family for generously supporting the theory seminar series


Hosts: Rachana Gusain, Rahul Madhavan, Rameesh Paul, KVN Sreenivas
DTSTART:20230623T120000Z
END:VEVENT
END:VCALENDAR