<div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-size:small"><div><div><div class="gmail_default" style="font-weight:bold"><font color="#000000" face="arial, helvetica, sans-serif">When: <span style="font-weight:400">    Wednesday, February 6th </span><span class="gmail-m_8275688149565729728gmail-m_1516749392281344011gmail-m_-2872424850751301179gmail-m_4851397928119953330gmail-m_-6533301490748126930gmail-m_659755472794929801gmail-m_-6461243813863673855gmail-m_-742000311328020925gmail-m_7559459027998801583gmail-m_4801029585485711767gmail-m_8517121454174849988gmail-m_-6691959996525573090gmail-m_1517372298344856049gmail-m_491069367152086750gmail-m_-8327640324523575189gmail-m_2420618808463760418gmail-m_7960197898027616883gmail-m_8692226636264124041gmail-m_2794822896869921223gmail-m_7508998950622620526gmail-m_-7153355664495542534gmail-il" style="font-weight:400">at</span><span style="font-weight:400"> </span><b>11:00 am</b></font></div><div class="gmail_default"><font color="#000000" face="arial, helvetica, sans-serif"><br></font></div><div class="gmail_default" style="font-weight:bold"><font color="#000000" face="arial, helvetica, sans-serif">Where:<span style="font-weight:400">    </span><span class="gmail-m_8275688149565729728gmail-m_1516749392281344011gmail-m_-2872424850751301179gmail-m_4851397928119953330gmail-m_-6533301490748126930gmail-m_659755472794929801gmail-m_-6461243813863673855gmail-m_-742000311328020925gmail-m_7559459027998801583gmail-m_4801029585485711767gmail-m_8517121454174849988gmail-m_-6691959996525573090gmail-m_1517372298344856049gmail-m_491069367152086750gmail-m_-8327640324523575189gmail-m_2420618808463760418gmail-m_7960197898027616883gmail-m_8692226636264124041gmail-m_2794822896869921223gmail-m_7508998950622620526gmail-m_-7153355664495542534gmail-m_8421504075585210435gmail-m_3262824545120381495gmail-m_-1141671822915777344gmail-m_-7219251726624328345gmail-m_-8588148075564318222gmail-m_-8767966813928691312gmail-m_-1542318334608687154gmail-m_5717104778280916634gmail-m_4845490158781220632gmail-m_5124567205141626540gmail-m_3209361100497750746gmail-m_2953668934074478317gmail-m_-3155518689668024534m_9067904842688472155gmail-m_3071693547520408192gmail-il" style="font-weight:400"><span class="gmail-m_8275688149565729728gmail-m_1516749392281344011gmail-m_-2872424850751301179gmail-m_4851397928119953330gmail-m_-6533301490748126930gmail-m_659755472794929801gmail-m_-6461243813863673855gmail-m_-742000311328020925gmail-m_7559459027998801583gmail-m_4801029585485711767gmail-m_8517121454174849988gmail-m_-6691959996525573090gmail-m_1517372298344856049gmail-m_491069367152086750gmail-m_-8327640324523575189gmail-m_2420618808463760418gmail-m_7960197898027616883gmail-m_8692226636264124041gmail-m_2794822896869921223gmail-m_7508998950622620526gmail-m_-7153355664495542534gmail-il"><span class="gmail-m_8275688149565729728gmail-m_1516749392281344011gmail-m_-2872424850751301179gmail-m_4851397928119953330gmail-m_-6533301490748126930gmail-m_659755472794929801gmail-m_-6461243813863673855gmail-m_-742000311328020925gmail-m_7559459027998801583gmail-m_4801029585485711767gmail-il">TTIC</span></span></span><span style="font-weight:400">, 6045 S Kenwood Avenue, 5th Floor, Room 526</span></font></div><div class="gmail_default"><font face="arial, helvetica, sans-serif"><br></font></div><font face="arial, helvetica, sans-serif"><span style="font-weight:bold;color:rgb(0,0,0)">Who:</span><span style="color:rgb(0,0,0)">       </span><font color="#000000">Jakub Tarnawski, </font><span style="color:rgb(33,33,33)">EPFL</span><br class="gmail-m_8275688149565729728gmail-Apple-interchange-newline"></font></div><div><b><font face="arial, helvetica, sans-serif"><br></font></b></div><div><b><font face="arial, helvetica, sans-serif"><br></font></b></div><div><font face="arial, helvetica, sans-serif"><b>Title:      </b>Towards Better Algorithms for Fundamental Optimization Problems</font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><b><font face="arial, helvetica, sans-serif">Abstract:</font></b></div><div><font face="arial, helvetica, sans-serif">The constant growth in the sizes of modern datasets, combined with an increasing reliance on algorithms in all areas of life, makes the rigorous study of algorithms more relevant than ever and necessitates the development of new algorithmic techniques. In this talk, I will show how ideas and tools from the theory of polyhedra and linear programming can be applied to make progress in fundamental optimization problems on graphs.</font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif">The focus of my talk will be the asymmetric version of the traveling salesman problem (ATSP), which consists in finding the shortest tour that visits all vertices of a given directed graph with weights (costs) on edges. I will show the main ideas that lead to the first constant-factor approximation algorithm for ATSP. In particular, I will explain a generic reduction to structured instances that resemble but are more general than those arising from unweighted graphs. This reduction takes advantage of a laminar family of vertex sets that arises from the standard linear programming relaxation.</font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif">I will also briefly discuss a new deterministic parallel algorithm for finding matchings in graphs. The algorithm is obtained by a derandomization of the celebrated Isolation Lemma by Mulmuley, Vazirani and Vazirani in the context of perfect matchings, and its analysis heavily depends on the laminar structure of the faces of the perfect matching polytope.</font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif"><b>Bio:</b><br></font></div><div><font face="arial, helvetica, sans-serif"><span class="gmail-m_8275688149565729728gmail-il">Jakub</span> <span class="gmail-m_8275688149565729728gmail-il">Tarnawski</span> is a doctoral student in the Theory of Computation laboratory at the EPFL, advised by Ola Svensson. He is broadly interested in theoretical computer science and combinatorial optimization, particularly in graph algorithms and approximation algorithms. He is a recipient of the Best Paper Award at STOC 2018 for his work on the traveling salesman problem, and of the Best Paper Award at FOCS 2017 for his work on matchings.  </font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif">Host: <a href="mailto:avrim@ttic.edu" target="_blank">Avrim Blum</a></font></div></div><div><br></div><div class="gmail-m_8275688149565729728gmail-yj6qo gmail-m_8275688149565729728gmail-ajU" style="outline:none;padding:10px 0px;width:22px;margin:2px 0px 0px"><br></div><br class="gmail-Apple-interchange-newline"></div><div><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><font face="arial, helvetica, sans-serif">Mary C. Marre</font><div><font face="arial, helvetica, sans-serif">Administrative Assistant</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">6045 S. Kenwood Avenue</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Room 517</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i></div><div><i><font face="arial, helvetica, sans-serif">p:(773) 834-1757</font></i></div><div><i><font face="arial, helvetica, sans-serif">f: (773) 357-6970</font></i></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div></div></div></div></div></div></div></div></div><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Jan 30, 2019 at 9:56 PM Mary Marre <<a href="mailto:mmarre@ttic.edu">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div><div><div><div style="font-weight:bold"><font color="#000000" face="arial, helvetica, sans-serif">When: <span style="font-weight:400">    Wednesday, February 6th </span><span class="gmail-m_8275688149565729728gmail-m_1516749392281344011gmail-m_-2872424850751301179gmail-m_4851397928119953330gmail-m_-6533301490748126930gmail-m_659755472794929801gmail-m_-6461243813863673855gmail-m_-742000311328020925gmail-m_7559459027998801583gmail-m_4801029585485711767gmail-m_8517121454174849988gmail-m_-6691959996525573090gmail-m_1517372298344856049gmail-m_491069367152086750gmail-m_-8327640324523575189gmail-m_2420618808463760418gmail-m_7960197898027616883gmail-m_8692226636264124041gmail-m_2794822896869921223gmail-m_7508998950622620526gmail-m_-7153355664495542534gmail-il" style="font-weight:400">at</span><span style="font-weight:400"> </span><b>11:00 am</b></font></div><div><font color="#000000" face="arial, helvetica, sans-serif"><br></font></div><div style="font-weight:bold"><font color="#000000" face="arial, helvetica, sans-serif">Where:<span style="font-weight:400">    </span><span class="gmail-m_8275688149565729728gmail-m_1516749392281344011gmail-m_-2872424850751301179gmail-m_4851397928119953330gmail-m_-6533301490748126930gmail-m_659755472794929801gmail-m_-6461243813863673855gmail-m_-742000311328020925gmail-m_7559459027998801583gmail-m_4801029585485711767gmail-m_8517121454174849988gmail-m_-6691959996525573090gmail-m_1517372298344856049gmail-m_491069367152086750gmail-m_-8327640324523575189gmail-m_2420618808463760418gmail-m_7960197898027616883gmail-m_8692226636264124041gmail-m_2794822896869921223gmail-m_7508998950622620526gmail-m_-7153355664495542534gmail-m_8421504075585210435gmail-m_3262824545120381495gmail-m_-1141671822915777344gmail-m_-7219251726624328345gmail-m_-8588148075564318222gmail-m_-8767966813928691312gmail-m_-1542318334608687154gmail-m_5717104778280916634gmail-m_4845490158781220632gmail-m_5124567205141626540gmail-m_3209361100497750746gmail-m_2953668934074478317gmail-m_-3155518689668024534m_9067904842688472155gmail-m_3071693547520408192gmail-il" style="font-weight:400"><span class="gmail-m_8275688149565729728gmail-m_1516749392281344011gmail-m_-2872424850751301179gmail-m_4851397928119953330gmail-m_-6533301490748126930gmail-m_659755472794929801gmail-m_-6461243813863673855gmail-m_-742000311328020925gmail-m_7559459027998801583gmail-m_4801029585485711767gmail-m_8517121454174849988gmail-m_-6691959996525573090gmail-m_1517372298344856049gmail-m_491069367152086750gmail-m_-8327640324523575189gmail-m_2420618808463760418gmail-m_7960197898027616883gmail-m_8692226636264124041gmail-m_2794822896869921223gmail-m_7508998950622620526gmail-m_-7153355664495542534gmail-il"><span class="gmail-m_8275688149565729728gmail-m_1516749392281344011gmail-m_-2872424850751301179gmail-m_4851397928119953330gmail-m_-6533301490748126930gmail-m_659755472794929801gmail-m_-6461243813863673855gmail-m_-742000311328020925gmail-m_7559459027998801583gmail-m_4801029585485711767gmail-il">TTIC</span></span></span><span style="font-weight:400">, 6045 S Kenwood Avenue, 5th Floor, Room 526</span></font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><font face="arial, helvetica, sans-serif"><font><span style="font-weight:bold;color:rgb(0,0,0)">Who:</span><span style="color:rgb(0,0,0)">       </span></font><font color="#000000">Jakub Tarnawski, </font><span style="color:rgb(33,33,33)">EPFL</span><br class="gmail-m_8275688149565729728gmail-Apple-interchange-newline"></font></div><div><b><font face="arial, helvetica, sans-serif"><br></font></b></div><div><b><font face="arial, helvetica, sans-serif"><br></font></b></div><div><font face="arial, helvetica, sans-serif"><b>Title:      </b>Towards Better Algorithms for Fundamental Optimization Problems</font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><b><font face="arial, helvetica, sans-serif">Abstract:</font></b></div><div><font face="arial, helvetica, sans-serif">The constant growth in the sizes of modern datasets, combined with an increasing reliance on algorithms in all areas of life, makes the rigorous study of algorithms more relevant than ever and necessitates the development of new algorithmic techniques. In this talk, I will show how ideas and tools from the theory of polyhedra and linear programming can be applied to make progress in fundamental optimization problems on graphs.</font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif">The focus of my talk will be the asymmetric version of the traveling salesman problem (ATSP), which consists in finding the shortest tour that visits all vertices of a given directed graph with weights (costs) on edges. I will show the main ideas that lead to the first constant-factor approximation algorithm for ATSP. In particular, I will explain a generic reduction to structured instances that resemble but are more general than those arising from unweighted graphs. This reduction takes advantage of a laminar family of vertex sets that arises from the standard linear programming relaxation.</font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif">I will also briefly discuss a new deterministic parallel algorithm for finding matchings in graphs. The algorithm is obtained by a derandomization of the celebrated Isolation Lemma by Mulmuley, Vazirani and Vazirani in the context of perfect matchings, and its analysis heavily depends on the laminar structure of the faces of the perfect matching polytope.</font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif"><b>Bio:</b><br></font></div><div><font face="arial, helvetica, sans-serif"><span class="gmail-m_8275688149565729728gmail-il">Jakub</span> <span class="gmail-m_8275688149565729728gmail-il">Tarnawski</span> is a doctoral student in the Theory of Computation laboratory at the EPFL, advised by Ola Svensson. He is broadly interested in theoretical computer science and combinatorial optimization, particularly in graph algorithms and approximation algorithms. He is a recipient of the Best Paper Award at STOC 2018 for his work on the traveling salesman problem, and of the Best Paper Award at FOCS 2017 for his work on matchings.  </font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif">Host: <a href="mailto:avrim@ttic.edu" target="_blank">Avrim Blum</a></font></div></div><div style="font-size:small"><br></div><div class="gmail-m_8275688149565729728gmail-yj6qo gmail-m_8275688149565729728gmail-ajU" style="font-size:small;outline:none;padding:10px 0px;width:22px;margin:2px 0px 0px"><br></div><div class="gmail-m_8275688149565729728gmail-yj6qo gmail-m_8275688149565729728gmail-ajU" style="font-size:small;outline:none;padding:10px 0px;width:22px;margin:2px 0px 0px"><br></div><div class="gmail-m_8275688149565729728gmail-yj6qo gmail-m_8275688149565729728gmail-ajU" style="font-size:small;outline:none;padding:10px 0px;width:22px;margin:2px 0px 0px"><br></div><div class="gmail-m_8275688149565729728gmail-yj6qo gmail-m_8275688149565729728gmail-ajU" style="font-size:small;outline:none;padding:10px 0px;width:22px;margin:2px 0px 0px"><br></div></div><div><div dir="ltr" class="gmail-m_8275688149565729728gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><font face="arial, helvetica, sans-serif">Mary C. Marre</font><div><font face="arial, helvetica, sans-serif">Administrative Assistant</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">6045 S. Kenwood Avenue</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Room 517</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i></div><div><i><font face="arial, helvetica, sans-serif">p:(773) 834-1757</font></i></div><div><i><font face="arial, helvetica, sans-serif">f: (773) 357-6970</font></i></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div>
</blockquote></div></div>