Professor Sepehr Assadi and his international collaborators — Soheil Behnezhad, Sayan Bhattacharya, Martín Costa, Shay Solomon and Tianyi Zhang — have received a Best Paper Award at STOC 2025, the 57th ACM Symposium on Theory of Computing.
Held annually since 1969, STOC covers all areas of research within algorithms and complexity theory and is one of the two most prestigious conferences in theoretical computer science. The award recognizes the research team’s paper, Vizing’s Theorem in Near-Linear Time, which introduces a randomized algorithm that computes a (∆ + 1)-edge colouring in near-linear time with high probability, a near-optimal result for this classic problem in graph theory.
“STOC Best Paper Awards are an exceptional recognition for research that is both novel and significant in the field of theoretical computer science,” said Raouf Boutaba, University Professor and Director of the Cheriton School of Computer Science. “Sepehr and his colleagues have achieved an outstanding result, showing that edge colouring — a foundational problem in graph theory — can be solved efficiently in near-linear time.”
Sepehr Assadi is an Associate Professor and a Faculty of Mathematics Research Chair at the Cheriton School of Computer Science. His research interest is in theoretical computer science and primarily algorithm design and complexity theory for modern models of computation. This includes sublinear algorithms and lower bounds in various models for processing massive datasets such as streaming, distributed, massively parallel, and sublinear time algorithms. He is also interested in graph theory, communication complexity, online algorithms, and algorithmic game theory.
Understanding Vizing’s theorem
Imagine a network of cities connected by roads. In graph theory, each city is a vertex, and each road an edge. The challenge is to assign a colour to each road so that no two roads meeting at the same city share the same colour. Additionally, we would like to use the smallest possible number of colours for this task.
Suppose the busiest city (vertex) in the network has Δ roads (edges) connected to it. Or, in more technical terms, let Δ denote the maximum degree of the graph. It is easy to see that at the very least we need Δ colours for colouring the network to ensure that no two roads incident on the busiest city have the same colours. It is also easy to see that in general, we may not always be able to colour the network with precisely Δ colours: consider a trio of cities all connected to each other via direct roads — one clearly cannot colour all roads in this network with only two colours and ensure no two roads meeting at the same city share the same colour, even though Δ = 2 in this network.
So then, what’s the minimum number of colours required to colour every graph?
This question is effectively answered by Vizing’s theorem, a foundational result in graph theory formulated by mathematician Vadim Vizing in 1964. Vizing’s theorem states that any graph can have its edges coloured using at most Δ + 1 colours — that is with just one more colour than its maximum degree. In other words, Δ colours are always necessary in any graph and Vizing’s theorem states Δ + 1 colours are also always sufficient. By now, Vizing’s theorem has been recognized as a fundamental theorem in graph theory and appears in most textbooks or courses in this area.
But, in addition to knowing every graph can be coloured Δ + 1 colours, we are also interested in designing algorithms that can find such a colouring of every given graph as fast as possible. This is the topic of a long line of research in algorithm design.
About this award-winning research
Vizing’s original proof also implies an algorithm for finding an edge colouring with Δ + 1 colours in O(mn) time — here, m is the number of edges in the graph and n is the number of vertices (this algorithm is described in detail in articles by Rao and Dijkstra, and by Misra and Gries, both from 1992). Later refinements improved this to (nearly) O(m√n) time, independently discovered by Eshrat Arjomandi in 1982 and by Harold Gabow, Takao Nishizeki, Oded Kariv, Daneil Leven and Osamu Terada in 1985. (These algorithms were further simplified and analyzed more carefully by Corwin Sinammon in 2019.)
The O(m√n) runtime for this problem remained a longstanding barrier for nearly four decades until very recently. In 2024, independently and concurrently, using randomization, this runtime bound was further improved to Õ(n2) by Sepehr Assadi and to Õ(mn1/3) by Sayan Bhattacharya, Din Carmon, Martín Costa, Shay Solomon and Tianyi Zhang. Even more recently and subsequent to these developments, the latter algorithm was further improved to Õ(mn1/4) time by Sayan Bhattacharya, Martín Costa, Shay Solomon and Tianyi Zhang in 2025.
The team’s STOC 2025 award-winning paper now effectively concludes this long line of research. They present a randomized algorithm that computes a (∆ + 1)-edge colouring in only O(m log ∆) time, with high probability. Modulo a small factor of log ∆, which is almost negligible in this context, this runtime is now as fast as simply reading the entire input once! This development represents a near-optimal solution for this fundamental problem in graph theory.