# Zihan Tan's Homepage

### I am a postdoc at DIMACS, Rutgers University. I obtained my PhD from University of Chicago, where I was advised by Prof. Julia Chuzhoy. You can find my CV here (last updated: Apr 2024).

### My research interests lie in theoretical computer science, and more specifically graph algorithms. My research focuses on developing modern algorithms for processing massive graphs, especially from the following three aspects:

### (i) exploring the limit of graph compression;

### (ii) studying graph problems in modern computational models (e.g. sublinear, dynamic, distributed); and

### (iii) designing approximation algorithms for fundamental graph problems by exploring the interplay between structural graph theory and graph algorithms.

### I co-organized the DIMACS Workshop on Modern Techniques in Graph Algorithms in June 2023 (with Nicole Wein and Prantar Ghosh). Check out the list of videos here.

### Email: zihantan1993 at gmail dot com

# Publications

Yu Chen, Zihan Tan.

Cut-Preserving Vertex Sparsifiers for Planar and Quasi-bipartite Graphs

Bernhard Haeupler, D Ellis Hershkowitz, Zihan Tan.

New Structures and Algorithms for Length-Constrained Expander Decompositions

Symposium on Foundations of Computer Science (FOCS 2024)

Yu Chen, Zihan Tan.

Lower Bounds on 0-Extension with Steiner Nodes

International Colloquium on Automata, Languages and Programming (ICALP 2024)

Yu Chen, Zihan Tan.

Towards the Characterization of Terminal Cut Functions: a Condition for Laminar Families

Yu Chen, Zihan Tan.

On (1+ε)-Approximate Flow Sparsifiers

Symposium on Discrete Algorithms (SODA 2024)

Yu Chen, Zihan Tan.

An \sqrt{\log |T|} Lower Bound for Steiner Point Removal

Symposium on Discrete Algorithms (SODA 2024)

Bernhard Haeupler, D Ellis Hershkowitz, Zihan Tan.

Parallel Greedy Spanners

Yu Chen, Sanjeev Khanna, Zihan Tan.

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

International Colloquium on Automata, Languages and Programming (ICALP 2023)

Zihan Tan, Tianyi Zhang.

Almost Optimal Sublinear Additive Spanners

Symposium on Theory of Computing (STOC 2023) [video by Tianyi]

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)

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

[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

On (1+ε)-Approximate Flow Sparsifiers

### Theory Seminar at Boston College, Oct 2023

### Theory Seminar at Weizmann Institute of Science, Oct 2023

Almost Optimal Sublinear Additive Spanners

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