Tianyi Zhang

tianyiz21 [at] tauex [dot] tau [dot] ac [dot] il

I am Tianyi Zhang, a postdoctoral fellow at Tel Aviv University, supervised by Prof. Shay Solomon, and previously supervised 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. Here is my CV.

I study graph algorithms.

Papers [Google Scholar]

  1. Nearly Optimal Approximate Dual-Failure Replacement Paths [slides, SIAM]
    Shiri Chechik, Tianyi Zhang
    Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024)

  2. Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-f Time Barrier [arxiv]
    Anton Bukov, Shay Solomon, Tianyi Zhang

  3. Streaming Edge Coloring with Subquadratic Palette Size [arxiv]
    Shiri Chechik, Doron Mukhtar, Tianyi Zhang

  4. Almost-Optimal 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

  5. 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)

  6. 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)

  7. 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)

  8. 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)

  9. 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)

  10. 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)

  11. Deterministic Maximum Flows in Simple Graphs [slides, LIPIcs]
    Tianyi Zhang
    Proceedings of the 48th EATCS International Colloquium on Automata, Languages and Programming (ICALP 2021)

  12. 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)

  13. 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)

  14. 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)

  15. 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)

  16. 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)

  17. 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)

  18. 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)

  19. Purely Combinatorial Algorithms for Approximate Directed Minimum Degree Spanning Trees [arxiv]
    Ran Duan, Tianyi Zhang

  20. Improved Distance Sensitivity Oracles via Tree Partitioning [arxiv, slides, Springer]
    Ran Duan, Tianyi Zhang
    Proceedsings of the Algorithms and Data Structures Symposium (WADS 2017)