Greg Bodwin, Bernhard Haeupler, D Ellis Hershkowits, Zihan Tan.
Simple Length-Constrained Expander Decompositions
SIAM Symposium on Simplicity in Algorithms (SOSA 2026)
Yu Chen, Zihan Tan, Hangyu Xu.
Lower Bounds on Tree Covers
George Z. Li, Zihan Tan, Tianyi Zhang.
Paths and Intersections: Exact Emulators for Planar Graphs
Symposium on Foundations of Computer Science (FOCS 2025)
Moses Charikar, Prasanna Ramakrishnan, Zihan Tan, Kangning Wang.
Metric Distortion for Tournament Voting and Beyond
ACM Conference on Economics and Computation (EC 2025)
Greg Bodwin, Gary Hoppenworth, Zihan Tan.
Multiplicative Spanners in Minor-Free Graphs
Yu Chen, Zihan Tan.
Cut-Preserving Vertex Sparsifiers for Planar and Quasi-bipartite Graphs
International Colloquium on Automata, Languages and Programming (ICALP 2025)
Yu Chen, Zihan Tan.
Paths and Intersections: Characterization of Quasi-metrics in Directed Okamura-Seymour Instances
Symposium on Discrete Algorithms (SODA 2025)
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]
SIAM Journal on Computing (Special Issue for STOC 2023), 215-249, 2024
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