天美传媒

We really enjoyed celebrating with our fantastic graduating students on Friday. If you have Instagram you can to see the highlights!

We would like to wish all our graduates all the best in their future work or study.

Click the link to view our 2024/25 prize winners.

We are delighted to announce that a result coauthored by and (from our Theory and Foundations Research Division), along with (University of Waterloo), (Northeastern University), (Tel Aviv University) and (ETH Zurich), has received a best paper award at the upcoming (STOC), 2025. STOC is a flagship international conference in theoretical computer science.

The paper, titled "," tackles a fundamental, textbook edge-coloring problem: Given a graph G with n vertices and m edges, the goal is to assign a color to each edge such that no two edges sharing a common endpoint receive the same color. A classical result by Vizing, dating back to 1960s, proves that any simple graph can always be edge-colored with at most 螖 + 1 colors, where 螖 is the maximum degree of a vertex. Vizing's original proof is inherently algorithmic and immediately gives an O(mn) time algorithm for computing such a coloring.

This problem has seen a long and influential line of research aimed at designing faster algorithms for this basic task. For over four decades, the best-known runtime was 脮(m鈭歯), a significant barrier that was only broken in 2024 through concurrent, independent works. The recent paper culminates this effort by providing a randomized algorithm that computes a 螖 + 1 edge coloring in O(m log 螖) time, a running time that is near-linear in the input size.