<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body>
<div class="" style="word-wrap:break-word"><span class="" style="font-size:14.666666984558105px">This is an announcement of Zihan Tan's Dissertation Defense.</span><br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">===============================================</span><br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">Candidate: Zihan Tan</span><br class="" style="font-size:14.666666984558105px">
<br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">Date: Monday, April 25, 2022</span><br class="" style="font-size:14.666666984558105px">
<br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">Time: 2 pm CST</span><br class="" style="font-size:14.666666984558105px">
<br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">Remote Location: Zoom Link: </span><a href="https://uchicago.zoom.us/j/97442905405?pwd=L0lrcUdKT3N2NkJLMzd3RmtLQStmZz09" class="" style="font-size:14.666666984558105px">https://uchicago.zoom.us/j/97442905405?pwd=L0lrcUdKT3N2NkJLMzd3RmtLQStmZz09</a><span class="" style="font-size:14.666666984558105px"> Meeting
ID：974 4290 5405 Passcode：260447</span><br class="" style="font-size:14.666666984558105px">
<br class="" style="font-size:14.666666984558105px">
<br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">Title: From Structural Graph Theory To Graph Algorithms, And Back</span><br class="" style="font-size:14.666666984558105px">
<br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">Abstract: In this thesis we study two algorithmic problems on graphs: Graph Crossing Number and the Packing of Low-Diameter Spanning Trees.</span><br class="" style="font-size:14.666666984558105px">
<br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">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 class="" style="font-size:14.666666984558105px">
<br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">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 class="" style="font-size:14.666666984558105px">
<br class="" style="font-size:14.666666984558105px">
<br class="" style="font-size:14.666666984558105px">
<br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">Advisors: Laci Babai and Julia Chuzhoy</span><br class="" style="font-size:14.666666984558105px">
<br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">Committee Members: Julia Chuzhoy, Laci Babai, and Lorenzo Orecchia</span>
<div class=""><span class="" style="font-size:14.666666984558105px"><br class="">
</span></div>
<div class=""></div>
</div>
<div class="" style="word-wrap:break-word">
<div class=""></div>
<div class=""><span class="" style="font-size:14.666666984558105px"><br class="">
</span></div>
</div>
</body>
</html>