# Zihan Tan's Homepage

### I am a postdoc at DIMACS, Rutgers University. I obtained my PhD from University of Chicago, where I am advised by Prof. Julia Chuzhoy. I am a 2019-2020 Siebel Scholar, and I am also the recipient of the 2021-2022 William Rainey Harper Dissertation Fellowship. You can find my CV here (last updated: Jan 2023).

### I am broadly interested in theoretical computer science. My research focuses on designing algorithms and proving lower bounds for combinatorial optimization problems. Currently I am working on problems in graph theory and graph algorithms.

### I am co-organizing the DIMACS Workshop on Modern Techniques in Graph Algorithms, which will be in June 2023.

### Email: zihantan1993 at gmail dot com

# Publications

Zihan Tan, Tianyi Zhang.

Almost Optimal Sublinear Additive Spanners

Symposium on Theory of Computing (STOC 2023).

Zihan Tan, Yifeng Teng, Mingfei Zhao.

Worst-Case Welfare of Item Pricing in the Tollbooth Problem

ACM Web Conference (WWW 2023)

Julia Chuzhoy, Mina Dalirrooyfard, Vadim Grinberg, Zihan Tan.

A New Conjecture on Hardness of Low-Degree 2-CSP’s with Implications to Hardness of Densest k-Subgraph and Other Problems

Innovations in Theoretical Computer Science (ITCS 2023).

Yu Chen, Sanjeev Khanna, Zihan Tan.

Query Complexity of the Metric Steiner Tree Problem

Symposium on Discrete Algorithms (SODA 2023).

Yu Chen, Sanjeev Khanna, Zihan Tan.

Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics

Julia Chuzhoy, Zihan Tan.

A Subpolynomial Approximation Algorithm for Graph Crossing Number in Low-Degree Graphs

Symposium on Theory of Computing (STOC 2022).

Hsien-Chih Chang, Robert Krauthgamer, Zihan Tan.

Near Linear \eps-Emulators for Planar Graphs

Symposium on Theory of Computing (STOC 2022).

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

### Mathematical Programming, Series B, 1-30, 2022

### Zihan Tan.

### On the Computational Complexity of Bridgecard

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

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

A New Conjecture on Hardness of Low-Degree 2-CSP’s with Implications to Hardness of Densest k-Subgraph and Other Problems