# Zihan Tan's Homepage

### I am a 6th year graduate student at the Department of Computer Science of The University of Chicago, where I am advised by Prof. Julia Chuzhoy and Prof. Laszlo Babai. Before coming to The University of Chicago, I received a Bachelor's degree in computer science and a Bachelor's degree in mathematics from Tsinghua University. I am a 2019-2020 Siebel Scholar. Here is my CV (last update: Aug 2021).

I am a 6th year graduate student at the Department of Computer Science of The University of Chicago, where I am advised by Prof. Julia Chuzhoy and Prof. Laszlo Babai. Before coming to The University of Chicago, I received a Bachelor's degree in computer science and a Bachelor's degree in mathematics from Tsinghua University. I am a 2019-2020 Siebel Scholar. Here is my CV (last update: Aug 2021).

### I have a broad research interest in theoretical computer science. My research focuses on algorithms and combinatorial optimization. Currently I am working on problems in graph theory and graph algorithms.

I have a broad research interest in theoretical computer science. My research focuses on algorithms and combinatorial optimization. Currently I am working on problems in graph theory and graph algorithms.

**I am applying for postdoc positions this year.**

**I am applying for postdoc positions this year.**

### Email: zihantan at uchicago dot edu

Email: zihantan at uchicago dot edu

# News

News

### I gave a virtual talk at Symposium on Discrete Algorithms (SODA 2021) on our recent work The Expander Hierarchy and its Applications to Dynamic Graph Algorithms.

I gave a virtual talk at Symposium on Discrete Algorithms (SODA 2021) on our recent work The Expander Hierarchy and its Applications to Dynamic Graph Algorithms.

### I gave a virtual talk at Symposium on Foundations of Computer Science (FOCS 2020) on our recent work Towards Better Approximation of Graph Crossing Number.

I gave a virtual talk at Symposium on Foundations of Computer Science (FOCS 2020) on our recent work Towards Better Approximation of Graph Crossing Number.

### I gave a virtual talk at Virtual Discrete Math Colloquium at IBS Discrete Mathematics Group of Institute for Basic Science on our work Towards Tight(er) Bounds for the Excluded Grid Theorem.

I gave a virtual talk at Virtual Discrete Math Colloquium at IBS Discrete Mathematics Group of Institute for Basic Science on our work Towards Tight(er) Bounds for the Excluded Grid Theorem.

### I gave a virtual talk at International Colloquium on Automata, Languages and Programming (ICALP 2020) on our recent work On Packing Low-Diameter Spanning Trees.

I gave a virtual talk at International Colloquium on Automata, Languages and Programming (ICALP 2020) on our recent work On Packing Low-Diameter Spanning Trees.

### I gave a talk at Seminar at Center on Frontiers of Computing Studies of Peking University on our recent work Towards Tight(er) Bounds for the Excluded Grid Theorem.

I gave a talk at Seminar at Center on Frontiers of Computing Studies of Peking University on our recent work Towards Tight(er) Bounds for the Excluded Grid Theorem.

### I gave a talk at Microsoft Research Asia on our recent work On Packing Low-Diameter Spanning Trees.

I gave a talk at Microsoft Research Asia on our recent work On Packing Low-Diameter Spanning Trees.

### I gave a talk at Seminar at Institute for Theoretical Computer Science of Shanghai University of Finance and Economics on our recent work On Packing Low-Diameter Spanning Trees.

I gave a talk at Seminar at Institute for Theoretical Computer Science of Shanghai University of Finance and Economics on our recent work On Packing Low-Diameter Spanning Trees.

### I gave a talk at Foundations of Computer Science Seminar in Faculty of Mathematics and Computer Science of The Weizmann Institute of Science on our recent work Towards Tight(er) Bounds for the Excluded Grid Theorem.

I gave a talk at Foundations of Computer Science Seminar in Faculty of Mathematics and Computer Science of The Weizmann Institute of Science on our recent work Towards Tight(er) Bounds for the Excluded Grid Theorem.

### I gave a talk at Theory Lunch in Computer Science Department of Technion - Israel Institute of Technology on our recent work Towards Tight(er) Bounds for the Excluded Grid Theorem.

I gave a talk at Theory Lunch in Computer Science Department of Technion - Israel Institute of Technology on our recent work Towards Tight(er) Bounds for the Excluded Grid Theorem.

### I gave a talk at Algorithm Seminar in School of Computer Science of Tel Aviv University on our recent work Towards Tight(er) Bounds for the Excluded Grid Theorem.

I gave a talk at Algorithm Seminar in School of Computer Science of Tel Aviv University on our recent work Towards Tight(er) Bounds for the Excluded Grid Theorem.

### I was a visiting student at Faculty of Mathematics and Computer Science of The Weizmann Institute of Science from Dec 2018 to Apr 2019.

I was a visiting student at Faculty of Mathematics and Computer Science of The Weizmann Institute of Science from Dec 2018 to Apr 2019.

### I gave a short talk at Symposium on Discrete Algorithms (SODA 2019) on our recent work Towards Tight(er) Bounds for the Excluded Grid Theorem.

I gave a short talk at Symposium on Discrete Algorithms (SODA 2019) on our recent work Towards Tight(er) Bounds for the Excluded Grid Theorem.

# Publications

Publications

Zihan Tan, Yifeng Teng, Mingfei Zhao

Worst-Case Welfare of Item Pricing in the Tollbooth Problem

### Gramoz Goranci, Harald Räcke, Thatchaphol Saranurak, Zihan Tan

Gramoz Goranci, Harald Räcke, Thatchaphol Saranurak, Zihan Tan

### The Expander Hierarchy and its Applications to Dynamic Graph Algorithms

The Expander Hierarchy and its Applications to Dynamic Graph Algorithms

### Symposium on Discrete Algorithms (SODA 2021).

Symposium on Discrete Algorithms (SODA 2021).

### Julia Chuzhoy, Sepideh Mahabadi, Zihan Tan

Julia Chuzhoy, Sepideh Mahabadi, Zihan Tan

### Towards Better Approximation of Graph Crossing Number

Towards Better Approximation of Graph Crossing Number

### Symposium on Foundations of Computer Science (FOCS 2020).

Symposium on Foundations of Computer Science (FOCS 2020).

### Julia Chuzhoy, Merav Parter, Zihan Tan

Julia Chuzhoy, Merav Parter, Zihan Tan

### On Packing Low-Diameter Spanning Trees

On Packing Low-Diameter Spanning Trees

### International Colloquium on Automata, Languages and Programming (ICALP 2020).

International Colloquium on Automata, Languages and Programming (ICALP 2020).

### Zihan Tan, Liwei Zeng.

Zihan Tan, Liwei Zeng.

### On the Inequalities of Projected Volumes and the Constructible Region

On the Inequalities of Projected Volumes and the Constructible Region

### SIAM Journal on Discrete Mathematics 33 (2), 694-711, 2019.

SIAM Journal on Discrete Mathematics 33 (2), 694-711, 2019.

### Julia Chuzhoy, Zihan Tan.

Julia Chuzhoy, Zihan Tan.

### Towards Tight(er) Bounds for the Excluded Grid Theorem

Towards Tight(er) Bounds for the Excluded Grid Theorem

### Symposium on Discrete Algorithms (SODA 2019).

Symposium on Discrete Algorithms (SODA 2019).

### Journal of Combinatorial Theory, Series B, 146, 219-265, 2021.

Journal of Combinatorial Theory, Series B, 146, 219-265, 2021.

### Wei Chen, Tian Lin, Zihan Tan, Mingfei Zhao, Xuren Zhou.

Wei Chen, Tian Lin, Zihan Tan, Mingfei Zhao, Xuren Zhou.

### Robust Influence Maximization

Robust Influence Maximization

### ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2016).

ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2016).

### Ioannis Caragiannis, Aris Filos-Ratsikas, Soren Stiil Frederiksen, Kristoffer Arnsfelt Hansen and Zihan Tan.

Ioannis Caragiannis, Aris Filos-Ratsikas, Soren Stiil Frederiksen, Kristoffer Arnsfelt Hansen and Zihan Tan.

### Truthful Facility Assignment with Resource Augmentation: An Exact Analysis of Serial Dictatorship

Truthful Facility Assignment with Resource Augmentation: An Exact Analysis of Serial Dictatorship

### The 12th Conference on Web and Internet Economics (WINE 2016).

The 12th Conference on Web and Internet Economics (WINE 2016).

### Zihan Tan.

Zihan Tan.

### On the Computational Complexity of Bridgecard

On the Computational Complexity of Bridgecard

### Journal of Combinatorial Optimization 31 (1), 196-217, 2016.

Journal of Combinatorial Optimization 31 (1), 196-217, 2016.

### [PDF]

[PDF]

### Jiachen Huang, Zihan Tan, Shenghao Yang, Xuan Guang.

Jiachen Huang, Zihan Tan, Shenghao Yang, Xuan Guang.

### Upper Bound on Function Computation in Directed Acyclic Networks

Upper Bound on Function Computation in Directed Acyclic Networks

### IEEE Information Theory Workshop (ITW 2015);

IEEE Information Theory Workshop (ITW 2015);

### IEEE Transactions on Information Theory 64 (9), 6454-6459, 2018.

IEEE Transactions on Information Theory 64 (9), 6454-6459, 2018.

### Yizhen Zhang, Zihan Tan, Bhaskar Krishnamachari.

Yizhen Zhang, Zihan Tan, Bhaskar Krishnamachari.

### On the Meeting Time for Two Random Walks on a Regular Graph, 2014

On the Meeting Time for Two Random Walks on a Regular Graph, 2014

# Talks and Slides

Talks and Slides

### Symposium on Discrete Algorithms (SODA 2021), online, Jan 2021 [video link]

Symposium on Discrete Algorithms (SODA 2021), online, Jan 2021 [video link]

### Symposium on Foundations of Computer Science (FOCS 2020), online, Oct 2020 [video link]

Symposium on Foundations of Computer Science (FOCS 2020), online, Oct 2020 [video link]

### Institute for Basic Science, South Korea, online, Sep 2020.

Institute for Basic Science, South Korea, online, Sep 2020.

### Peking University, Beijing, Sep 2019.

Peking University, Beijing, Sep 2019.

### The Weizmann Institute of Science, Rehovot, Apr 2019.

The Weizmann Institute of Science, Rehovot, Apr 2019.

### Technion - Israel Institute of Technology, Haifa, Mar 2019.

Technion - Israel Institute of Technology, Haifa, Mar 2019.

### Tel Aviv University, Tel Aviv, Mar 2019.

Tel Aviv University, Tel Aviv, Mar 2019.

### Symposium on Discrete Algorithms (SODA 2019), San Diego, Jan 2019.

Symposium on Discrete Algorithms (SODA 2019), San Diego, Jan 2019.

### The University of Chicago, Chicago, Sep 2018.

The University of Chicago, Chicago, Sep 2018.

### International Colloquium on Automata, Languages and Programming (ICALP 2020), online, Jun 2020 [video link].

International Colloquium on Automata, Languages and Programming (ICALP 2020), online, Jun 2020 [video link].

### Shanghai University of Finance and Economics, Shanghai, Sep 2019.

Shanghai University of Finance and Economics, Shanghai, Sep 2019.

### Microsoft Research Asia, Sep 2019.

Microsoft Research Asia, Sep 2019.

### On the Inequalities of Projected Volumes and the Constructible Region

On the Inequalities of Projected Volumes and the Constructible Region

### The Chinese University of Hong Kong, Jan 2016.

The Chinese University of Hong Kong, Jan 2016.

# Conference Review

Conference Review