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

arXiv:2407.10852


Bernhard Haeupler, D Ellis Hershkowitz, Zihan Tan.

New Structures and Algorithms for Length-Constrained Expander Decompositions

Symposium on Foundations of Computer Science (FOCS 2024)

arXiv:2404.13446


Yu Chen, Zihan Tan.

Lower Bounds on 0-Extension with Steiner Nodes

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

arXiv:2401.09585


Yu Chen, Zihan Tan.

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

arXiv:2310.11367


Yu Chen, Zihan Tan.

On (1+ε)-Approximate Flow Sparsifiers

Symposium on Discrete Algorithms (SODA 2024)

arXiv:2310.07857


Yu Chen, Zihan Tan.

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

Symposium on Discrete Algorithms (SODA 2024)

arXiv:2310.07862


Bernhard Haeupler, D Ellis Hershkowitz, Zihan Tan.

Parallel Greedy Spanners

arXiv:2304.08892


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)

arXiv:2203.14798


Zihan Tan, Tianyi Zhang.

Almost Optimal Sublinear Additive Spanners

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

arXiv:2303.12768


Zihan Tan, Yifeng Teng, Mingfei Zhao.

Worst-Case Welfare of Item Pricing in the Tollbooth Problem

ACM Web Conference (WWW 2023)

arXiv:2107.05690.


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)

arXiv: 2211.05906


Yu Chen, Sanjeev Khanna, Zihan Tan.

Query Complexity of the Metric Steiner Tree Problem

Symposium on Discrete Algorithms (SODA 2023)

arXiv: 2211.03893


Julia Chuzhoy, Zihan Tan.

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

Symposium on Theory of Computing (STOC 2022)

arXiv:2202.06827.


Hsien-Chih Chang, Robert Krauthgamer, Zihan Tan.

Near Linear ε-Emulators for Planar Graphs

Symposium on Theory of Computing (STOC 2022)

arXiv:2206.10681.


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)

arXiv:2005.02369.


Julia Chuzhoy, Sepideh Mahabadi, Zihan Tan.

Towards Better Approximation of Graph Crossing Number

Symposium on Foundations of Computer Science (FOCS 2020)

arXiv:2011.06545.


Julia Chuzhoy, Merav Parter, Zihan Tan.

On Packing Low-Diameter Spanning Trees

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

arXiv:2006.07486.


Zihan Tan, Liwei Zeng.

On the Inequalities of Projected Volumes and the Constructible Region

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

arXiv:1410.8663.


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

arXiv:1901.07944.


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

Robust Influence Maximization

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

arXiv:1601.06551.


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

arXiv:1602.08023.


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

arXiv:1501.01084.


Yizhen Zhang, Zihan Tan, Bhaskar Krishnamachari.

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

arXiv:1408.2005.



Talks and Slides


On (1+ε)-Approximate Flow Sparsifiers

Symposium on Discrete Algorithms (SODA 2024), Jan 2024

Junior Theorists Workshop 2023 at Northwestern University, Nov 2023

Algorithm and Theory Seminar at Boston University, Oct 2023

Theory Seminar at Boston College, Oct 2023

Theory Seminar at Brown, Oct 2023 [video link]

Theory Seminar at Weizmann Institute of Science, Oct 2023

Theory Seminar at UIUC, Oct 2023

Algorithm Seminar at Duke, Oct 2023

CATS Seminar at University of Maryland, Oct 2023

Theory Lunch at Columbia University, Sep 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


Workshop on Local Algorithms (WOLA 2022), online, Jun 2022


28th Atlanta Lecture Series, Georgia Tech, Mar 2024

ACM Symposium on Theory of Computing (STOC 2022), online, Jun 2022 [video link]


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


CS Theory Seminar at UPenn, Mar 2023

CS Theory Lunch at Princeton, Feb 2023

CSDM Seminar II at IAS, Jan 2023

CS Theory Seminar at Northeastern University, online, Jan 2023

Crossing Number Workshop, online, July 2022

ACM Symposium on Theory of Computing (STOC 2022), online, Jun 2022 [video link]

Theory Seminar at Northwestern University, Apr 2022

Theory Lunch at CMU, online, Feb 2022 [video link]

Algorithm & Complexity Seminar at MIT, online, Jan 2022


Virtual Discrete Math Colloquium at IBS Discrete Mathematics Group of Institute for Basic Science, online, Sep 2020.

Seminar at Center on Frontiers of Computing Studies of Peking University, Sep 2019.

Foundations of Computer Science Seminar at the Weizmann Institute of Science, Apr 2019.

Theory Lunch in Computer Science Department of Technion - Israel Institute of Technology, Mar 2019.

Algorithm Seminar in School of Computer Science of Tel Aviv University, Mar 2019.

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


Seminar at Institute for Theoretical Computer Science of Shanghai University of Finance and Economics, Sep 2019.


On the Inequalities of Projected Volumes and the Constructible Region

The Chinese University of Hong Kong, Jan 2016.