<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<style type="text/css" style="display:none;"> P {margin-top:0;margin-bottom:0;} </style>
</head>
<body dir="ltr">
<div style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);" class="elementToProof">
<span style="caret-color:rgb(0, 0, 0);font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto;display:inline !important">This is an announcement of Zihan Tan's Dissertation Defense.</span><br style="caret-color:rgb(0, 0, 0);font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto">
<span style="caret-color:rgb(0, 0, 0);font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto;display:inline !important">===============================================</span><br style="caret-color:rgb(0, 0, 0);font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto">
<span style="caret-color:rgb(0, 0, 0);font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto;display:inline !important">Candidate: Zihan Tan</span><br style="caret-color:rgb(0, 0, 0);font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto">
<br style="caret-color:rgb(0, 0, 0);font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto">
<span style="caret-color:rgb(0, 0, 0);font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto;display:inline !important">Date: Monday, April 25, 2022</span><br style="caret-color:rgb(0, 0, 0);font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto">
<br style="caret-color:rgb(0, 0, 0);font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto">
<span style="caret-color:rgb(0, 0, 0);font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto;display:inline !important">Time: 2 pm CST</span><br style="caret-color:rgb(0, 0, 0);font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto">
<br style="caret-color:rgb(0, 0, 0);font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto">
<span style="caret-color:rgb(0, 0, 0);font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto;display:inline !important">Remote Location: Zoom Link:<span class="Apple-converted-space"> </span></span><a href="https://uchicago.zoom.us/j/97442905405?pwd=L0lrcUdKT3N2NkJLMzd3RmtLQStmZz09" style="font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto">https://uchicago.zoom.us/j/97442905405?pwd=L0lrcUdKT3N2NkJLMzd3RmtLQStmZz09</a><span style="caret-color:rgb(0, 0, 0);font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto;display:inline !important"><span class="Apple-converted-space"> </span>Meeting
ID：974 4290 5405 Passcode：260447</span><br style="caret-color:rgb(0, 0, 0);font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto">
<br style="caret-color:rgb(0, 0, 0);font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto">
<br style="caret-color:rgb(0, 0, 0);font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto">
<span style="caret-color:rgb(0, 0, 0);font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto;display:inline !important">Title: From Structural Graph Theory To Graph Algorithms, And Back</span><br style="caret-color:rgb(0, 0, 0);font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto">
<br style="caret-color:rgb(0, 0, 0);font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto">
<span style="caret-color:rgb(0, 0, 0);font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto;display:inline !important">Abstract: In this thesis we study two algorithmic problems on graphs: Graph Crossing Number and
the Packing of Low-Diameter Spanning Trees.</span><br style="caret-color:rgb(0, 0, 0);font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto">
<br style="caret-color:rgb(0, 0, 0);font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto">
<span style="caret-color:rgb(0, 0, 0);font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto;display:inline !important">In the first part of the thesis, we consider the Graph Crossing Number problem, in which we are
given a graph and are asked to find a drawing of it in the plane that minimizes the number of crossings. For bounded-degree graphs, almost all previous algorithms followed the same framework, and the best of them achieved an Õ(⎷n)-approximation, which was
also proved to be optimal in this framework. We propose a new framework that overcomes this barrier. This allows us to reduce the problem to another related problem called the Crossing Number with Rotation System problem, and eventually obtain an n^o(1)-approximation
for the Crossing Number problem on low-degree graphs.</span><br style="caret-color:rgb(0, 0, 0);font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto">
<br style="caret-color:rgb(0, 0, 0);font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto">
<span style="caret-color:rgb(0, 0, 0);font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto;display:inline !important">In the second part of this thesis, we study the problem of packing low-diameter spanning trees.
The celebrated tree-packing theorem due to Tutte and Nash-Williams states that every 2k-edge-connected graph contains k edge-disjoint spanning trees. We use the techniques of randomized algorithms to show that every 2k-edge-connected graph with diameter D
contains k spanning trees with diameter k^O(D) each, that cause edge-congestion 2. We then show that the same techniques can be applied to improve the Karger's edge-sampling theorem. Finally, we use these graph-theoretic results to improve the round complexities
of various distributed graph algorithms.</span><br style="caret-color:rgb(0, 0, 0);font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto">
<br style="caret-color:rgb(0, 0, 0);font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto">
<br style="caret-color:rgb(0, 0, 0);font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto">
<br style="caret-color:rgb(0, 0, 0);font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto">
<span style="caret-color:rgb(0, 0, 0);font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto;display:inline !important">Advisors: Laci Babai and Julia Chuzhoy</span><br style="caret-color:rgb(0, 0, 0);font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto">
<br style="caret-color:rgb(0, 0, 0);font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto">
<span style="caret-color:rgb(0, 0, 0);font-family:Helvetica;font-size:14.666666984558105px;font-weight:normal;orphans:auto;widows:auto;display:inline !important">Committee Members: Julia Chuzhoy, Laci Babai, and Lorenzo Orecchia</span><br>
</div>
</body>
</html>