BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:The Subspace Flatness Conjecture and Faster Integer Programming [O
 berseminar Discrete Optimization]
DTSTART:20250512T161500Z
DTEND:20250512T171500Z
DTSTAMP:20260513T140500Z
UID:indico-event-143@math-events.uni-bonn.de
DESCRIPTION:Speakers: Thomas Rothvoß (University of Washington)\n\nIn a s
 eminal paper\, Kannan and Lovász (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 Lov
 ´asz proved that μ(Λ\, K) ≤ n · μKL(Λ\, K) and the Subspace Flatne
 ss Conjecture by Dadush (2012) claims a O(log n) factor suffices\, which w
 ould 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 μ(Λ\, 
 K) ≤ O(log3(n)) · μKL(Λ\, K). Our proof is based on the Reverse Minko
 wski Theorem due to Regev and Stephens-Davidowitz (2017). Following the wo
 rk of Dadush (2012\, 2019)\, we obtain a (log n)O(n)-time randomized algor
 ithm to solve integer programs in n variables.Another implication of our m
 ain result is a near-optimal flatness constant of O(n log3(n)).\nThis is j
 oint work with Victor Reis.\n \n\nhttps://math-events.uni-bonn.de/event/1
 43/
LOCATION:Arithmeum\, Lennéstr.\,  2 - Seminarraum (Arithmeum / Research I
 nstitute for Discrete Mathematics)
URL:https://math-events.uni-bonn.de/event/143/
END:VEVENT
END:VCALENDAR