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.

The University held its annual research celebration earlier this week. At the event, Adrian Fowle was announced as one of the winners of the “Research Enabler” award for 2025. This is a very well deserved recognition - Congratulations, Adrian!

A new paper has been published in the Royal Society of Chemistry journal Energy & Environmental Science by postdoc Yi Yuan, which has been selected as a ‘Research Highlight’ by Nature Energy due to its importance in the field.

Epidemiologist Dr Matt Combes was recently interviewed for the Guardian about Ash die-back in the UK and the scientific efforts to protect ash trees. The publication highlights Matt's review article on ash die-back and his more recent work at Warwick modelling the severity of the disease and how this may interact with the emerald ash borer beetle. The modelling is part of the SMARTIES (Surveillance and Management of multiple Risks to Treescapes: Integrating Epidemiology and Stakeholder behaviour) project.
Read the Guardian article (20 December 2024).
Photograph: Andy Soloman/Alamy

Huge congratulations to Dr Richard Montgomery and Professor Ewelina Zatorska, who were both among the winners of this year's London Mathematical Society Whitehead Prizes. Dr Montgomery won for his outstanding work on the absorption method, and on sublinear expanders, in extremal and probabilistic combinatorics, while Professor Zatorska for her deep and lasting contributions to the mathematical theory of the compressible Navier–Stokes equations and other nonlinear partial differential equations. A full list of winners can be found on the LMS websiteLink opens in a new window.

The EDITH trial (‘Early Detection using Information Technology in Health’) is backed by £11 million of government support via the National Institute for Health and Care Research (NIHR). It is the latest example of how British scientists are transforming cancer care, building on the promising potential of cutting-edge innovations to tackle one of the UK’s biggest killers. Read the full news item here.