{"670235":{"#nid":"670235","#data":{"type":"event","title":"Thomas Rothvoss Lectures on Integer Programming","body":[{"value":"\u003Cp\u003EWednesday October 18, 11am-12pm, Klaus 1116:\u0026nbsp; Introduction to Lattices;\u0026nbsp;\u0026nbsp;\u003Cbr \/\u003E\r\n---\u003Cbr \/\u003E\r\nIn this lecture, we will give a brief introduction to the lattices and discuss the seminal result\u003Cbr \/\u003E\r\nof Micciancio and Voulgaris (2010) that gives a 2^O(n) time algorithm for computing a closest vector.\u003Cbr \/\u003E\r\nWe will also discuss the result by Dadush and Vempala (2012) to enumerate all the lattice points\u003Cbr \/\u003E\r\nin a general convex body K in time 2^O(n) times the maximum number of points that any translate may contain.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cbr \/\u003E\r\nThursday October 19, 11am-12pm Klaus 2447: The Reverse Minkowski Theorem\u003C\/p\u003E\r\n\r\n\u003Cp\u003E---\u003Cbr \/\u003E\r\nWe explain the Reverse Minkowski Theorem due to Regev and Stephens-Davidowitz (2017). Formally the\u003Cbr \/\u003E\r\nresult states that for any lattice Lambda that does not contain a sublattice of determinant less than 1,\u003Cbr \/\u003E\r\nthe sum of Gaussian weights satisfies rho_1\/t(Lambda) \u0026lt;= 3\/2 where t = Theta(log n).\u003Cbr \/\u003E\r\nIn particular this implies that, any such lattice contains at most a quasi-polynomial number of vectors of length at most O(1).\u003Cbr \/\u003E\r\nThe result is based on advanced concepts from convex geometry.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cbr \/\u003E\r\nFriday October 20, 1pm-2pm, Skiles 005: The Subspace Flatness Conjecture and Faster Integer Programming\u003C\/p\u003E\r\n\r\n\u003Cp\u003E---\u003Cbr \/\u003E\r\nIn a seminal paper, Kannan and Lov\u00e1sz (1988) considered a quantity \u03bc_KL(\u039b,K) which denotes the best volume-based\u003Cbr \/\u003E\r\nlower bound on the covering radius \u03bc(\u039b,K) of a convex body K with respect to a lattice \u039b.\u003Cbr \/\u003E\r\nKannan and Lov\u00e1sz proved that \u03bc(\u039b,K)\u2264n\u22c5\u03bc_KL(\u039b,K) and the Subspace Flatness Conjecture by Dadush (2012) claims a O(log(n)) factor suffices,\u003Cbr \/\u003E\r\nwhich would match the lower bound from the work of Kannan and Lov\u00e1sz.\u003Cbr \/\u003E\r\nWe settle this conjecture up to a constant in the exponent by proving that \u03bc(\u039b,K)\u2264O(log^3(n))\u22c5\u03bc_KL(\u039b,K).\u003Cbr \/\u003E\r\nOur proof is based on the Reverse Minkowski Theorem due to Regev and Stephens-Davidowitz (2017).\u003Cbr \/\u003E\r\nFollowing the work of Dadush (2012, 2019), we obtain a (log(n))^O(n)-time randomized algorithm to solve\u003Cbr \/\u003E\r\ninteger programs in n variables. Another implication of our main result is a near-optimal flatness constant of O(n*log^3(n)).\u003C\/p\u003E\r\n","summary":"","format":"limited_html"}],"field_subtitle":"","field_summary":[{"value":"\u003Cp\u003EPart 1 - Introduction to Lattices\u003Cbr \/\u003E\r\nPart 2 - The Reverse Minkowski Theorem\u003Cbr \/\u003E\r\nPart 3 - The Subspace Flatness Conjecture and Faster Integer Programming\u003C\/p\u003E\r\n","format":"limited_html"}],"field_summary_sentence":[{"value":"Special ARC Lecture Series"}],"uid":"36512","created_gmt":"2023-10-06 11:54:08","changed_gmt":"2023-10-12 13:57:19","author":"wperkins3","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2023-10-18T07:49:31-04:00","event_time_end":"2023-10-20T08:49:31-04:00","event_time_end_last":"2023-10-20T08:49:31-04:00","gmt_time_start":"2023-10-18 11:49:31","gmt_time_end":"2023-10-20 12:49:31","gmt_time_end_last":"2023-10-20 12:49:31","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"},{"id":"177814","name":"Postdoc"},{"id":"174045","name":"Graduate students"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}