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.”
Read the full story from Computer Science to learn more.