{"344241":{"#nid":"344241","#data":{"type":"event","title":"ARC Colloquium: YinTat Lee - Massachusetts Institute of Technology","body":[{"value":"\u003Cp class=\u0022p1\u0022\u003E\u003Cstrong\u003ETea and light refreshments 2:00 pm in Klaus Room 2222\u003C\/strong\u003E\u003C\/p\u003E\u003Cp class=\u0022p2\u0022\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E\u0026nbsp;\u003Cbr \/\u003E A Faster Algorithm for Linear Programming\u003Cbr \/\u003E \u003Cbr \/\u003E \u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u0026nbsp;\u003Cbr \/\u003E In this talk I will present a new algorithm for solving linear programs. Given a linear program with n variables, m \u0026gt; n constraints, and bit complexity L, our algorithm runs in \u00d5(sqrt(n) L) iterations each consisting of solving \u00d5(1) linear systems and additional nearly linear time computation. Our method improves upon the convergence rate of previous state-of-the-art linear programming methods which required solving either \u00d5(sqrt(m)L) linear systems [R88] or consisted of \u00d5((mn)^(1\/4)) steps of more expensive linear algebra [VA93].\u0026nbsp;\u003Cbr \/\u003E \u003Cbr \/\u003E Interestingly, our algorithm not only nearly matches the convergence rate of the universal barrier of Nesterov and Nemirovskii [NN94], but in the special case of the linear programming formulation of various flow problems our methods converge at a rate faster than that predicted by any self-concordant barrier. In particular, we achieve a running time of \u00d5(|E| sqrt(|V| log^2 U) for solving the maximum flow problem on a directed graph with |E| edges, |V| vertices, and capacity ratio U, thereby improving upon the previous fastest running time for solving this problem when |E| \u0026gt; \u03a9(|V|^1+epsilon) for any constant epsilon.\u0026nbsp;\u003Cbr \/\u003E \u003Cbr \/\u003E This talk will assume little exposure to linear programming algorithms, convex optimization, or graph theory and will require no previous experience with the universal barrier or self-concordance.\u0026nbsp;\u003Cbr \/\u003E \u003Cbr \/\u003E This talk reflects joint work with Aaron Sidford.\u0026nbsp;\u003Cbr \/\u003E \u0026nbsp;See \u003Ca href=\u0022http:\/\/arxiv.org\/abs\/1312.6677\u0022 title=\u0022http:\/\/arxiv.org\/abs\/1312.6677\u0022\u003Ehttp:\/\/arxiv.org\/abs\/1312.6677\u003C\/a\u003E and \u003Ca href=\u0022http:\/\/arxiv.org\/abs\/1312.6713\u0022 title=\u0022http:\/\/arxiv.org\/abs\/1312.6713\u0022\u003Ehttp:\/\/arxiv.org\/abs\/1312.6713\u003C\/a\u003E\u003C\/p\u003E\u003Cp class=\u0022p2\u0022\u003E\u003Cstrong\u003EBio:\u003C\/strong\u003E\u003Cbr \/\u003E Yin Tat Lee is a PhD student (under Professor Jonathan Kelner) at MIT, studying theoretical computer science. His areas of research span convex optimization, linear programming, spectral graph theory and algorithmic graph theory. He is particularly interested in combining convex optimization and combinations techniques to design fast algorithms for fundamental cut\/flow problems. He is one of the recipients of the Best Paper Awards at SODA 2014, FOCS 2014 for his results on the maximum flow problem and linear programming.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"A Faster Algorithm for Linear Programming"}],"uid":"27998","created_gmt":"2014-11-11 10:20:13","changed_gmt":"2016-10-08 02:07:49","author":"Brittany Aiello","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2014-11-17T12:00:00-05:00","event_time_end":"2014-11-17T13:00:00-05:00","event_time_end_last":"2014-11-17T13:00:00-05:00","gmt_time_start":"2014-11-17 17:00:00","gmt_time_end":"2014-11-17 18:00:00","gmt_time_end_last":"2014-11-17 18:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[{"id":"2924","name":"MIT"},{"id":"109351","name":"Yin Tat Lee"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78771","name":"Public"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp class=\u0022p1\u0022\u003Edenton at cc dot gatech dot edu\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}