<div dir="ltr">Reminder:<div><br></div><div><br><div class="gmail_quote">---------- Forwarded message ----------<br>From: <b class="gmail_sendername">Mary Marre</b> <span dir="ltr"><<a href="mailto:mmarre@ttic.edu">mmarre@ttic.edu</a>></span><br>Date: Wed, Jun 20, 2018 at 11:50 AM<br>Subject: [TTIC Talks] REMINDER: 6/21 Thesis Defense: Haris Angelidakis, TTIC<br>To: TTIC Talks <<a href="mailto:talks@ttic.edu">talks@ttic.edu</a>>, <a href="mailto:theory@mailman.cs.uchicago.edu">theory@mailman.cs.uchicago.edu</a>, <a href="mailto:colloquium@cs.uchicago.edu">colloquium@cs.uchicago.edu</a>, Yury Makarychev <<a href="mailto:ymakarychev@gmail.com">ymakarychev@gmail.com</a>><br><br><br><div dir="ltr">
<div style="font-size:12.8px;text-decoration-style:initial;text-decoration-color:initial"><font face="arial, helvetica, sans-serif"><b>When:</b><span style="font-weight:bold"> </span><span class="m_-2851824734803863481gmail-m_1298675840749854666gmail-aBn" style="border-bottom:1px dashed rgb(204,204,204)"><span class="m_-2851824734803863481gmail-m_1298675840749854666gmail-aQJ">Thursday, June 21st at 10:00 am</span></span></font></div><div style="font-size:12.8px;text-decoration-style:initial;text-decoration-color:initial"><b><span class="m_-2851824734803863481gmail-m_1298675840749854666gmail-aBn" style="border-bottom:1px dashed rgb(204,204,204)"><span class="m_-2851824734803863481gmail-m_1298675840749854666gmail-aQJ"><font face="arial, helvetica, sans-serif"><br></font></span></span></b></div><div style="font-size:12.8px;text-decoration-style:initial;text-decoration-color:initial"><font face="arial, helvetica, sans-serif"><b>Where: <span> </span></b><span style="font-weight:bold"> </span><span class="m_-2851824734803863481gmail-m_1298675840749854666gmail-aBn" style="border-bottom:1px dashed rgb(204,204,204)"><span class="m_-2851824734803863481gmail-m_1298675840749854666gmail-aQJ">TTIC, <a href="https://maps.google.com/?q=6045+S.+Kenwood+Avenue,+5th+Floor,+Room+526&entry=gmail&source=g">6045 S. Kenwood Avenue, 5th Floor, Room 526</a></span></span></font></div><div style="font-size:12.8px;text-decoration-style:initial;text-decoration-color:initial"><b><span class="m_-2851824734803863481gmail-m_1298675840749854666gmail-aBn" style="border-bottom:1px dashed rgb(204,204,204)"><span class="m_-2851824734803863481gmail-m_1298675840749854666gmail-aQJ"><font face="arial, helvetica, sans-serif"><br></font></span></span></b></div><div style="font-size:12.8px;text-decoration-style:initial;text-decoration-color:initial"><font face="arial, helvetica, sans-serif"><b>Who: </b>Haris Angelidakis, TTIC</font></div><div style="font-size:12.8px;text-decoration-style:initial;text-decoration-color:initial"><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-size:12.8px;text-decoration-style:initial;text-decoration-color:initial"><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-size:12.8px;text-decoration-style:initial;text-decoration-color:initial"><font face="arial, helvetica, sans-serif"><b>Title: </b>Shortest Path Queries, Graph Partitioning and Covering Problems in Worst and Beyond Worst Case Settings</font></div><div style="font-size:12.8px;text-decoration-style:initial;text-decoration-color:initial"><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-size:12.8px;text-decoration-style:initial;text-decoration-color:initial"><b><u><font face="arial, helvetica, sans-serif">Abstract</font></u></b></div><div style="font-size:12.8px;text-decoration-style:initial;text-decoration-color:initial"><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif">In this<span> </span><span class="m_-2851824734803863481gmail-il">thesis</span>, we design algorithms for several NP-hard problems in both worst and beyond worst case settings. In the first part of the<span> </span><span class="m_-2851824734803863481gmail-il">thesis</span>, we apply the traditional worst case methodology and design approximation algorithms for the Hub Labeling problem; Hub Labeling is a preprocessing technique introduced to speed up shortest path queries. Before this work, Hub Labeling had been extensively studied mainly in the beyond worst case analysis setting, and in particular on graphs with low highway dimension (a notion introduced in order to explain why certain heuristics for shortest paths are very successful in real-life road networks). In this work, we significantly improve our theoretical understanding of the problem and design (worst-case) algorithms for various classes of graphs, such as general graphs, graphs with unique shortest paths and trees, as well as provide matching inapproximability lower bounds for the problem in its most general settings. Finally, we demonstrate a connection between computing a Hub Labeling on a tree and searching for a node in a tree.<br></font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif">In the second part of the<span> </span><span class="m_-2851824734803863481gmail-il">thesis</span>, we turn to beyond worst case analysis and extensively study the stability model introduced by Bilu and Linial in an attempt to describe real-life instances of graph partitioning and clustering problems. Informally, an instance of a combinatorial optimization problem is stable if it has a unique optimal solution that remains the unique optimum under small (multiplicative and adversarial) perturbations of the parameters of the input (e.g. edge or vertex weights). Utilizing the power of convex relaxations for stable instances, we obtain several results for problems such as Edge/Node Multiway Cut, Independent Set (and its equivalent, in terms of exact solvability, Vertex Cover), clustering problems such as k-center and k-median and the symmetric Traveling Salesman problem. We also provide strong lower bounds for certain families of algorithms for covering problems, thus exhibiting potential barriers towards the design of improved algorithms in this framework.</font></div></div><div style="font-size:12.8px;text-decoration-style:initial;text-decoration-color:initial"><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-size:12.8px;text-decoration-style:initial;text-decoration-color:initial"><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-size:12.8px;text-decoration-style:initial;text-decoration-color:initial"><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-size:12.8px;text-decoration-style:initial;text-decoration-color:initial"><font face="arial, helvetica, sans-serif"><span class="m_-2851824734803863481gmail-il">Thesis</span><span> </span>Advisor:<span> </span><a href="mailto:yury@ttic.edu" style="color:rgb(17,85,204)" target="_blank">Yury Makarychev </a><a href="mailto:yury@ttic.edu" style="color:rgb(17,85,204)" target="_blank"></a></font></div><font face="arial, helvetica, sans-serif" style="font-size:12.8px;text-decoration-style:initial;text-decoration-color:initial"><br class="m_-2851824734803863481gmail-m_1298675840749854666gmail-Apple-interchange-newline"><br></font>
<br><div class="gmail_extra"><br clear="all"><div><div class="m_-2851824734803863481gmail_signature" data-smartmail="gmail_signature"><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"><a href="https://maps.google.com/?q=6045+S.+Kenwood+Avenue+Room+504+Chicago,+IL+%C2%A060637&entry=gmail&source=g">6045 S. Kenwood Avenue</a></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><a href="https://maps.google.com/?q=6045+S.+Kenwood+Avenue+Room+504+Chicago,+IL+%C2%A060637&entry=gmail&source=g">Room 504</a></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><a href="https://maps.google.com/?q=6045+S.+Kenwood+Avenue+Room+504+Chicago,+IL+%C2%A060637&entry=gmail&source=g">Chicago, IL 60637</a></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>
<br><div class="gmail_quote">On Thu, Jun 14, 2018 at 4:12 PM, Mary Marre <span dir="ltr"><<a href="mailto:mmarre@ttic.edu" target="_blank">mmarre@ttic.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">
<div style="text-decoration-style:initial;text-decoration-color:initial"><font face="arial, helvetica, sans-serif"><b>When:</b><span style="font-weight:bold"> </span><span class="m_-2851824734803863481m_1298675840749854666gmail-aBn" style="border-bottom:1px dashed rgb(204,204,204)"><span class="m_-2851824734803863481m_1298675840749854666gmail-aQJ">Thursday, June 21st at 10:00 am</span></span></font></div><div style="text-decoration-style:initial;text-decoration-color:initial"><b><span class="m_-2851824734803863481m_1298675840749854666gmail-aBn" style="border-bottom:1px dashed rgb(204,204,204)"><span class="m_-2851824734803863481m_1298675840749854666gmail-aQJ"><font face="arial, helvetica, sans-serif"><br></font></span></span></b></div><div style="text-decoration-style:initial;text-decoration-color:initial"><font face="arial, helvetica, sans-serif"><b>Where: </b><span style="font-weight:bold"> </span><span class="m_-2851824734803863481m_1298675840749854666gmail-aBn" style="border-bottom:1px dashed rgb(204,204,204)"><span class="m_-2851824734803863481m_1298675840749854666gmail-aQJ">TTIC, <a href="https://maps.google.com/?q=6045+S.+Kenwood+Avenue,+5th+Floor,+Room+526&entry=gmail&source=g">6045 S. Kenwood Avenue, 5th Floor, Room 526</a></span></span></font></div><div style="text-decoration-style:initial;text-decoration-color:initial"><b><span class="m_-2851824734803863481m_1298675840749854666gmail-aBn" style="border-bottom:1px dashed rgb(204,204,204)"><span class="m_-2851824734803863481m_1298675840749854666gmail-aQJ"><font face="arial, helvetica, sans-serif"><br></font></span></span></b></div><div style="text-decoration-style:initial;text-decoration-color:initial"><font face="arial, helvetica, sans-serif"><b>Who: </b>Haris Angelidakis, TTIC</font></div><div style="text-decoration-style:initial;text-decoration-color:initial"><font face="arial, helvetica, sans-serif"><br></font></div><div style="text-decoration-style:initial;text-decoration-color:initial"><font face="arial, helvetica, sans-serif"><br></font></div><div style="text-decoration-style:initial;text-decoration-color:initial"><font face="arial, helvetica, sans-serif"><b>Title: </b>Shortest Path Queries, Graph Partitioning and Covering Problems in Worst and Beyond Worst Case Settings</font></div><div style="text-decoration-style:initial;text-decoration-color:initial"><font face="arial, helvetica, sans-serif"><br></font></div><div style="text-decoration-style:initial;text-decoration-color:initial"><b><u><font face="arial, helvetica, sans-serif">Abstract</font></u></b></div><div style="text-decoration-style:initial;text-decoration-color:initial"><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif">In this thesis, we design algorithms for several NP-hard problems in both worst and beyond worst case settings. In the first part of the thesis, we apply the traditional worst case methodology and design approximation algorithms for the Hub Labeling problem; Hub Labeling is a preprocessing technique introduced to speed up shortest path queries. Before this work, Hub Labeling had been extensively studied mainly in the beyond worst case analysis setting, and in particular on graphs with low highway dimension (a notion introduced in order to explain why certain heuristics for shortest paths are very successful in real-life road networks). In this work, we significantly improve our theoretical understanding of the problem and design (worst-case) algorithms for various classes of graphs, such as general graphs, graphs with unique shortest paths and trees, as well as provide matching inapproximability lower bounds for the problem in its most general settings. Finally, we demonstrate a connection between computing a Hub Labeling on a tree and searching for a node in a tree.<br></font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif">In the second part of the thesis, we turn to beyond worst case analysis and extensively study the stability model introduced by Bilu and Linial in an attempt to describe real-life instances of graph partitioning and clustering problems. Informally, an instance of a combinatorial optimization problem is stable if it has a unique optimal solution that remains the unique optimum under small (multiplicative and adversarial) perturbations of the parameters of the input (e.g. edge or vertex weights). Utilizing the power of convex relaxations for stable instances, we obtain several results for problems such as Edge/Node Multiway Cut, Independent Set (and its equivalent, in terms of exact solvability, Vertex Cover), clustering problems such as k-center and k-median and the symmetric Traveling Salesman problem. We also provide strong lower bounds for certain families of algorithms for covering problems, thus exhibiting potential barriers towards the design of improved algorithms in this framework.</font></div></div><div style="text-decoration-style:initial;text-decoration-color:initial"><font face="arial, helvetica, sans-serif"><br></font></div><div style="text-decoration-style:initial;text-decoration-color:initial"><font face="arial, helvetica, sans-serif"><br></font></div><div style="text-decoration-style:initial;text-decoration-color:initial"><font face="arial, helvetica, sans-serif"><br></font></div><div style="text-decoration-style:initial;text-decoration-color:initial"><font face="arial, helvetica, sans-serif">Thesis Advisor: <a href="mailto:yury@ttic.edu" target="_blank">Yury Makarychev </a><a href="mailto:yury@ttic.edu" target="_blank"></a></font></div><font face="arial, helvetica, sans-serif"><br class="m_-2851824734803863481m_1298675840749854666gmail-Apple-interchange-newline">
<br></font><br><br clear="all"><div><div class="m_-2851824734803863481m_1298675840749854666gmail_signature"><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"><a href="https://maps.google.com/?q=6045+S.+Kenwood+Avenue+Room+504+Chicago,+IL+%C2%A060637&entry=gmail&source=g">6045 S. Kenwood Avenue</a></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><a href="https://maps.google.com/?q=6045+S.+Kenwood+Avenue+Room+504+Chicago,+IL+%C2%A060637&entry=gmail&source=g">Room 504</a></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><a href="https://maps.google.com/?q=6045+S.+Kenwood+Avenue+Room+504+Chicago,+IL+%C2%A060637&entry=gmail&source=g">Chicago, IL 60637</a></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>
</blockquote></div><br></div></div>
</div><br></div></div>