Tianyi Zhang

I am Tianyi Zhang, a postdoctoral fellow at ETH Zürich, supervised by Prof. Rasmus Kyng. Previously, I was a postdoctoral fellow at Tel Aviv University, supervised by Prof. Shay Solomon during 2023-2024, by Prof. Shiri Chechik during 2021-2023. I received my PhD in computer science at Tsinghua University in 2021, advised by Prof. Ran Duan, and a BEng in computer science at Tsinghua University in 2016. I study graph algorithms. [CV] [Google Scholar]

Papers

Vizing’s Theorem in Near-Linear Time [arxiv, video by Martin]
Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martín Costa, Shay Solomon, Tianyi Zhang
Even Faster \((\Delta+1)\)-Edge Coloring via Shorter Multi-Step Vizing Chains [arxiv, SIAM]
Sayan Bhattacharya, Martín Costa, Shay Solomon, Tianyi Zhang
Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025)
Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-f Time Barrier [arxiv, SIAM]
Anton Bukov, Shay Solomon, Tianyi Zhang
Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025)
Towards Instance-Optimal Euclidean Spanners [arxiv, video by Cuong, IEEE]
Hung Le, Shay Solomon, Cuong Than, Csaba Toth, Tianyi Zhang
Proceedings of the IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS 2024)
A Lossless Deamortization for Dynamic Greedy Set Cover [arxiv, video by Amitai, IEEE]
Shay Solomon, Amitai Uzrad, Tianyi Zhang
Proceedings of the IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS 2024)
Faster \((\Delta+1)\)-Edge Coloring: Breaking the \(m\sqrt{n}\) Time Barrier [arxiv, video by Martin, slides at Dagstuhl, IEEE]
Sayan Bhattacharya, Din Carmon, Martín Costa, Shay Solomon, Tianyi Zhang
Proceedings of the IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS 2024)
Path-Reporting Distance Oracles with Logarithmic Stretch and Linear Size [slides by Shiri, LIPIcs]
Shiri Chechik, Tianyi Zhang
Proceedings of the 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP 2024)
Faster Algorithms for Dual-Failure Replacement Paths [arxiv, slides by Shiri, LIPIcs]
Shiri Chechik, Tianyi Zhang
Proceedings of the 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP 2024)
Streaming Edge Coloring with Subquadratic Palette Size [arxiv, LIPIcs]
Shiri Chechik, Doron Mukhtar, Tianyi Zhang
Proceedings of the 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP 2024)
Nearly Optimal Approximate Dual-Failure Replacement Paths [slides by Shiri, SIAM]
Shiri Chechik, Tianyi Zhang
Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024)
Almost-Optimal Sublinear Additive Spanners [arxiv, video, slides, ACM, SICOMP]
Zihan Tan, Tianyi Zhang
Proceedings of the 55th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2023)
Faster Deterministic Worst-Case Fully Dynamic All-Pairs Shortest Paths via Decremental Hop-Restricted Shortest Paths [slides, SIAM]
Shiri Chechik, Tianyi Zhang
Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)
Constant Approximation of Min-Distances in Near-Linear Time [slides, IEEE]
Shiri Chechik, Tianyi Zhang
Proceedings of the IEEE 63th Annual Symposium on Foundations of Computer Science (FOCS 2022)
Constant-Round Near-Optimal Spanners in Congested Clique [slides, ACM]
Shiri Chechik, Tianyi Zhang
Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing (PODC 2022)
Faster Cut-Equivalent Trees in Simple Graphs [arxiv, note, slides, LIPIcs]
Tianyi Zhang
Proceedings of the 49th EATCS International Colloquium on Automata, Languages and Programming (ICALP 2022)
Faster min-plus product for monotone instances [arxiv, video, slides, poster, ACM]
Shucheng Chi, Ran Duan, Tianle Xie, Tianyi Zhang
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2022)
Nearly 2-Approximate Distance Oracles in Subquadratic Time [slides, SIAM]
Shiri Chechik, Tianyi Zhang
Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2022)
Deterministic Maximum Flows in Simple Graphs [slides, LIPIcs]
Tianyi Zhang
Proceedings of the 48th EATCS International Colloquium on Automata, Languages and Programming (ICALP 2021)
Incremental Single Source Shortest Paths in Sparse Digraphs [slides, SIAM]
Shiri Chechik, Tianyi Zhang
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA 2021)
Near-Linear Time Algorithm for Approximate Minimum Degree Spanning Trees [arxiv, slides, Springer]
Ran Duan, Haoqing He, Tianyi Zhang
Proceedings of the 14th Latin American Theoretical Informatics Symposium (LATIN 2020)
A Scaling Algorithm for Weighted f-Factors in General Graphs [arxiv, video by Haoqing, LIPIcs]
Ran Duan, Haoqing He, Tianyi Zhang
Proceedings of the 47th EATCS International Colloquium on Automata, Languages and Programming (ICALP 2020)
Dynamic Low-Stretch Spanning Trees in Subpolynomial Time [slides, SIAM]
Shiri Chechik, Tianyi Zhang
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA 2020)
Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time [arxiv, video, slides, IEEE]
Shiri Chechik, Tianyi Zhang
Proceedings of the IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS 2019)
Dynamic Edge Coloring with Improved Approximation [slides, SIAM]
Ran Duan, Haoqing He, Tianyi Zhang
Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019)
An Improved Algorithm for Incremental DFS Tree in Undirected Graphs [arxiv, slides, LIPIcs]
Lijie Chen, Ran Duan, Ruosong Wang, Hanrui Zhang, Tianyi Zhang
Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Purely Combinatorial Algorithms for Approximate Directed Minimum Degree Spanning Trees [arxiv]
Ran Duan, Tianyi Zhang
Improved Distance Sensitivity Oracles via Tree Partitioning [arxiv, slides, Springer]
Ran Duan, Tianyi Zhang
Proceedsings of the Algorithms and Data Structures Symposium (WADS 2017)