Tianyi Zhang
tianyi [dot] zhang [at] inf [dot] ethz [dot] ch
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 20232024, by Prof. Shiri Chechik during 20212023. 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

Towards InstanceOptimal Euclidean Spanners [arxiv]
Proceedings of the IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS 2024, to appear)
Hung Le, Shay Solomon, Cuong Than, Csaba Toth, Tianyi Zhang 
A Lossless Deamortization for Dynamic Greedy Set Cover [arxiv]
Proceedings of the IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS 2024, to appear)
Shay Solomon, Amitai Uzrad, Tianyi Zhang 
Faster \((\Delta+1)\)Edge Coloring: Breaking the \(m\sqrt{n}\) Time Barrier [arxiv]
Proceedings of the IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS 2024, to appear)
Sayan Bhattacharya, Din Carmon, Martín Costa, Shay Solomon, Tianyi Zhang 
PathReporting Distance Oracles with Logarithmic Stretch and Linear Size [LIPIcs]
Proceedings of the 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP 2024)
Shiri Chechik, Tianyi Zhang 
Faster Algorithms for DualFailure Replacement Paths [arxiv, LIPIcs]
Proceedings of the 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP 2024)
Shiri Chechik, Tianyi Zhang 
Streaming Edge Coloring with Subquadratic Palette Size [arxiv, LIPIcs]
Proceedings of the 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP 2024)
Shiri Chechik, Doron Mukhtar, Tianyi Zhang 
Nearly Optimal Approximate DualFailure Replacement Paths [slides presented by Shiri, SIAM]
Shiri Chechik, Tianyi Zhang
Proceedings of the 2024 Annual ACMSIAM Symposium on Discrete Algorithms (SODA 2024) 
Nearly Optimal Dynamic Set Cover: Breaking the Quadraticinf Time Barrier [arxiv]
Anton Bukov, Shay Solomon, Tianyi Zhang 
AlmostOptimal Sublinear Additive Spanners [arxiv, video, slides, ACM]
Zihan Tan, Tianyi Zhang
Proceedings of the 55th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2023)
Invited to SICOMP Special Issue 
Faster Deterministic WorstCase Fully Dynamic AllPairs Shortest Paths via Decremental HopRestricted Shortest Paths [slides, SIAM]
Shiri Chechik, Tianyi Zhang
Proceedings of the 2023 Annual ACMSIAM Symposium on Discrete Algorithms (SODA 2023) 
Constant Approximation of MinDistances in NearLinear Time [slides, IEEE]
Shiri Chechik, Tianyi Zhang
Proceedings of the IEEE 63th Annual Symposium on Foundations of Computer Science (FOCS 2022) 
ConstantRound NearOptimal Spanners in Congested Clique [slides, ACM]
Shiri Chechik, Tianyi Zhang
Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing (PODC 2022) 
Faster CutEquivalent 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 minplus 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 2Approximate Distance Oracles in Subquadratic Time [slides, SIAM]
Shiri Chechik, Tianyi Zhang
Proceedings of the 2022 Annual ACMSIAM 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 ACMSIAM Symposium on Discrete Algorithms (SODA 2021) 
NearLinear 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 fFactors 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 LowStretch Spanning Trees in Subpolynomial Time [slides, SIAM]
Shiri Chechik, Tianyi Zhang
Proceedings of the 2020 ACMSIAM Symposium on Discrete Algorithms (SODA 2020) 
Fully Dynamic Maximal Independent Set in Expected PolyLog 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 ACMSIAM 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)