BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//UC Irvine Donald Bren School of Information & Computer Sciences - ECPv5.12.3//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:UC Irvine Donald Bren School of Information & Computer Sciences
X-ORIGINAL-URL:https://ics.uci.edu
X-WR-CALDESC:Events for UC Irvine Donald Bren School of Information & Computer Sciences
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:America/Los_Angeles
BEGIN:DAYLIGHT
TZOFFSETFROM:-0800
TZOFFSETTO:-0700
TZNAME:PDT
DTSTART:20240310T100000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0700
TZOFFSETTO:-0800
TZNAME:PST
DTSTART:20241103T090000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=America/Los_Angeles:20240201T140000
DTEND;TZID=America/Los_Angeles:20240201T150000
DTSTAMP:20240418T124039
CREATED:20240122T224849Z
LAST-MODIFIED:20240201T155514Z
UID:20331-1706796000-1706799600@ics.uci.edu
SUMMARY:The Subspace Flatness Conjecture and Faster Integer Programming
DESCRIPTION:Abstract: 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. \nWe 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\nbased 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))$. \nBio: Thomas Rothvoss is Professor of Mathematics & Computer Science at the University of Washington and works on questions in linear and integer programming\, discrepancy theory and approximation algorithms. He completed his PhD in Mathematics in 2009 at EPFL under Friedrich Eisenbrand\, followed by a PostDoc at MIT with Michel Goemans. He received a STOC 2010 Best Paper Award\, a SODA 2014 Best Paper Award\, a STOC 2014 Best Paper Award\, a FOCS 2023 Best Paper Award\, the 2018 Delbert Ray Fulkerson Prize and the 2023 G\”odel Prize. His research is supported by an Alfred P. Sloan Research Fellowship (2015)\, a David & Lucile Packard Foundation Fellowship (2016) as well as an NSF CAREER Award (2016).
URL:https://ics.uci.edu/event/the-subspace-flatness-conjecture-and-faster-integer-programming/
LOCATION:Donald Bren Hall\, Irvine\, CA\, 92697\, United States
ATTACH;FMTTYPE=image/jpeg:https://ics.uci.edu/wp-content/uploads/2024/01/Thomas-Rothvoss_resize.jpg
END:VEVENT
END:VCALENDAR