Computer 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.

A paper co-authored by Matthias C. Caro has been featured on the cover of PRX Quantum. PRX Quantum is a premier journal for quantum information science and technology research. The work was a collaboration with Haimeng Zhao (Caltech & Tsinghua), Laura Lewis (Caltech & Google), Ishaan Kannan (Caltech), Yihui Quek (Harvard & MIT) and Hsin-Yuan Huang (Caltech, Google & MIT).

Characterizing a quantum system by learning its state or unitary evolution is a key tool in developing quantum devices, with applications in practical quantum machine learning, benchmarking, and error mitigation. However, in general, this task requires exponentially many resources. Prior knowledge is required to circumvent this exponential bottleneck. The paper pinpoints the complexity for learning states and unitaries that can be implemented by quantum circuits with a bounded number of gates, a broad setting that is topical for current quantum technologies. When measuring efficiency with respect to the number of accesses to the unknown quantum state or unitary, the paper presents and implements algorithms that are provably optimally efficient. Thereby, this work establishes the equivalence between the complexity of learning quantum states or unitaries and the complexity of creating them. However, it also shows that the data processing necessarily requires exponential computation time under reasonable cryptographic assumptions.

We are happy to announce that an academic from our department, Dr Sayan Bhattacharya, is among the winners of ERC Consolidator Grants 2024. According to the European Research Council: "These grants, totalling €678 million, aim to support outstanding scientists and scholars as they establish their independent research teams and develop their most promising scientific ideas. The funding is provided through the EU's Horizon Europe programme."

Sayan Bhattacharya has been awarded a €2million ERC Consolidator grant for a 5-year project entitled "Towards a Dynamic Algorithms Centric Theory of Linear Programming" (DYNALP). The project aims to build a new theory exploring the interplay between two key concepts, Linear Programming and Dynamic Algorithms, which, in turn, will pave the way towards attacking outstanding open questions in the field of Theoretical Computer Science.

In the 2024 round, this was the only project from the United Kingdom that was awarded an ERC Consolidator Grant in Computer Science and Informatics (PE6 panel). The press release contains more information about the ERC funding programme.

We are delighted to announce that Martin Costa, a PhD student at the Theory and Foundations research division, has received a highly competitive Google PhD Fellowship for his work on designing clustering algorithms for dynamic datasets. The Fellowship comes in the form of an unrestricted gift from Google, of 60,000 USD per year, for up to two years. Under the category of "Algorithms and Theory", besides Martin only two other PhD students in Europe (from University of Cambridge and ETH Zurich) received a Google PhD Fellowship this year. Many congratulations to Martin for this achievement!

Neha Rino, a PhD student in the Theory and Foundations group in the Department of Computer Science and a member of the Cyber Security group at WMG, has won an Oded Maler award at FORMATS 2024.

The Oded Maler award is a distinction presented for the best paper of the International Conference on Formal Modeling and Analysis of Timed Systems (FORMATS). This year's edition of the conference was held in September in Calgary, Canada, jointly with QEST (International Conference on Quantitative Evaluation of SysTems) as a common research forum dedicated to quantitative modelling, analysis, and verification.

Neha's paper, "Efficiently Computable Distance-Based Robustness for a Practical Fragment of STL", is co-authored with Mohammed Foughali and Eugene Asarin, both from Université Paris Cité and IRIF in Paris, France, where Neha completed the Master's degree (ENS Paris-Saclay) prior to joining Warwick.

Neha's paper contributes to the research framework of quantitative monitoring, which is the analysis of individual executions of systems which yields numerical output (real numbers), rather than binary yes/no. The paper formulates and solves, by an efficient algorithm, a new problem of this kind: computing a real number that characterises to which extent the given execution of a real-time system satisfies its specification expressed in Signal Temporal Logic (STL).

PhD positions are available at the Theory and Foundations (FoCS) group in the Department of Computer Science, University of Warwick, UK. The group has strong ties with the Centre for Discrete Mathematics and its Applications (DIMAP), established in 2007 jointly with the Warwick Mathematics Institute and Warwick Business School. Together with DIMAP, the group is one of the leading theory groups in Europe, with regular publications in top international conferences and journals in theoretical computer science.

Many congratulations to Henry Sinclair-Banks for passing his PhD viva today, which was one of the shortest and best in the long memories of the examiners, Dr Richard Mayr from the University of Edinburgh, and our own Professor Ranko Lazic.