TZTianyi Zhang
Tianyi Zhang
*This is an algorithmically generated author record based on publicly available information.
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Tianyi Zhang has a total of 6 co-authors. Here are the top co-authors by number of shared publications:
- Martín Costa
University of Warwick, Coventry, United Kingdom
2 shared publications - Sayan Bhattacharya
University of Warwick
2 shared publications - Sepehr Assadi
University of Waterloo, Waterloo, Canada
2 shared publications - Shay Solomon
Tel Aviv University, Tel Aviv, Israel
2 shared publications - Soheil Behnezhad
Northeastern University, Boston, USA
2 shared publications - Zihan Tan
University of Minnesota, Minneapolis, USA
1 shared publication
Latest Publications
- Open Access
- 16 June 2026
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 73 (3) , 1-53
Vizing’s Theorem in Near-Linear Time
Vizing’s theorem states that any n -vertex m -edge graph of maximum degree Δ can be edge colored using at most Δ + 1 different colors [Vizing, 1964]. Vizing’s original proof is algorithmic and shows that such an edge coloring can be found in O(mn) time. This was subsequently improved to \(\tilde{O}(m\sqrt {n})\) time, independently by [Arjomandi, 1982] and by [Gabow et al., 1985]. 1 Very recently, independently and concurrently, using randomization, this runtime bound was further improved to \(\tilde{O}(n^2)\) by [Assadi, 2024] and \(\tilde{O}(mn^{1/3})\) by [Bhattacharya, Carmon, Costa, Solomon and Zhang, 2024] (and subsequently to \(\tilde{O}(mn^{1/4})\) by [Bhattacharya, Costa, Solomon and Zhang, 2024]). In this article, we present a randomized algorithm that computes a Δ + 1-edge coloring in near-linear time—in fact, only O(m log Δ) time—with high probability, giving a near-optimal algorithm for this fundamental problem .- 16 June 2026
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 73 (3) , 1-53
Open AccessVizing’s Theorem in Near-Linear Time
Vizing’s theorem states that any n -vertex m -edge graph of maximum degree Δ can be edge colored using at most Δ + 1 different colors [Vizing, 1964]. Vizing’s original proof is algorithmic and shows that such an edge coloring can be found in O(mn) time. This was subsequently improved to \(\tilde{O}(m\sqrt {n})\) time, independently by [Arjomandi, 1982] and by [Gabow et al., 1985]. 1 Very recently, independently and concurrently, using randomization, this runtime bound was further improved to \(\tilde{O}(n^2)\) by [Assadi, 2024] and \(\tilde{O}(mn^{1/3})\) by [Bhattacharya, Carmon, Costa, Solomon and Zhang, 2024] (and subsequently to \(\tilde{O}(mn^{1/4})\) by [Bhattacharya, Costa, Solomon and Zhang, 2024]). In this article, we present a randomized algorithm that computes a Δ + 1-edge coloring in near-linear time—in fact, only O(m log Δ) time—with high probability, giving a near-optimal algorithm for this fundamental problem . - Open Access
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 24-35
Vizing’s Theorem in Near-Linear Time
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 24-35
Open AccessVizing’s Theorem in Near-Linear Time
- 2 December 2024
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- p. STOC23-215
Almost-Optimal Sublinear Additive Spanners
- 2 December 2024
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- p. STOC23-215
Almost-Optimal Sublinear Additive Spanners