Data Science News

We are delighted to announce that a result coauthored by Sayan Bhattacharya and Martin Costa (from our Theory and Foundations Research Division), along with Sepehr Assadi (University of Waterloo), Soheil Behnezhad (Northeastern University), Shay Solomon (Tel Aviv University) and Tianyi Zhang (ETH Zurich), has received a best paper award at the upcoming ACM Symposium on Theory of Computing (STOC), 2025. STOC is a flagship international conference in theoretical computer science.

The paper, titled "Vizing's Theorem in Near-Linear Time," 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√n), 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.

We are excited to share that our team “TIAKong” secured leading positions in the recent PUMALink opens in a new window (Panoptic segmentation of nuclei and tissue in advanced Melanoma) Challenge, organized by the Department of Medical Oncology, University Medical Center Utrecht, in the Netherlands. With over 300 participants from around the globe, this challenge aimed to advance automated panoptic segmentation techniques for H&E-stained melanoma tissue images.

Led by our PhD students Jiaqi Lv and YiJie Zhu, and supported by Brinder Singh Chohan, Shan E Ahmed Raza, with an external collaborator Carmen Guadalupe Colin Tenorio from the Medical University of Vienna. TIAKong achieved first place in Track 1 and second place in Track 2. This outstanding performance underscores the team’s dedication to pushing the boundaries of medical imaging and improving our understanding of advanced melanoma.

We look forward to building on these results and sharing further developments of our panoptic segmentation model in the near future.