[Colloquium] Reminder - Zihan Tan Dissertation Defense/Apr 25, 2022

[Megan Woodward]

This is an announcement of Zihan Tan's Dissertation Defense.
===============================================
Candidate: Zihan Tan

Date: Monday, April 25, 2022

Time:  2 pm CST

Remote Location: Zoom Link: https://uchicago.zoom.us/j/97442905405?pwd=L0lrcUdKT3N2NkJLMzd3RmtLQStmZz09 Meeting ID：974 4290 5405 Passcode：260447


Title: From Structural Graph Theory To Graph Algorithms, And Back

Abstract: In this thesis we study two algorithmic problems on graphs: Graph Crossing Number and the Packing of Low-Diameter Spanning Trees.

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.

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.



Advisors: Laci Babai and Julia Chuzhoy

Committee Members: Julia Chuzhoy, Laci Babai, and Lorenzo Orecchia


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20220425/4698cda8/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: main.pdf
Type: application/pdf
Size: 1894315 bytes
Desc: main.pdf
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20220425/4698cda8/attachment-0001.pdf>