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

  1. Towards Instance-Optimal 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

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

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

  4. Path-Reporting 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

  5. Faster Algorithms for Dual-Failure Replacement Paths [arxiv, LIPIcs]
    Proceedings of the 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP 2024)
    Shiri Chechik, Tianyi Zhang

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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