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 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.

Email: zihantan at uchicago dot edu

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 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 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 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 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 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 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


Zihan Tan, Yifeng Teng, Mingfei Zhao

Worst-Case Welfare of Item Pricing in the Tollbooth Problem

arXiv:2107.05690


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

The Expander Hierarchy and its Applications to Dynamic Graph Algorithms

Symposium on Discrete Algorithms (SODA 2021).


Julia Chuzhoy, Sepideh Mahabadi, Zihan Tan

Towards Better Approximation of Graph Crossing Number

Symposium on Foundations of Computer Science (FOCS 2020).


Julia Chuzhoy, Merav Parter, Zihan Tan

On Packing Low-Diameter Spanning Trees

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


Zihan Tan, Liwei Zeng.

On the Inequalities of Projected Volumes and the Constructible Region

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


Julia Chuzhoy, Zihan Tan.

Towards Tight(er) Bounds for the Excluded Grid Theorem

Symposium on Discrete Algorithms (SODA 2019).

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


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

Robust Influence Maximization

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.

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

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


Zihan Tan.

On the Computational Complexity of Bridgecard

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

[PDF]


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

Upper Bound on Function Computation in Directed Acyclic Networks

IEEE Information Theory Workshop (ITW 2015);

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


Yizhen Zhang, Zihan Tan, Bhaskar Krishnamachari.

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



Talks and Slides


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


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


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

Peking University, Beijing, Sep 2019.

The Weizmann Institute of Science, Rehovot, Apr 2019.

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

Tel Aviv University, Tel Aviv, Mar 2019.

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

The University of Chicago, Chicago, Sep 2018.


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

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

Microsoft Research Asia, Sep 2019.


On the Inequalities of Projected Volumes and the Constructible Region

The Chinese University of Hong Kong, Jan 2016.