We are delighted to announce that the paper "Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time", coauthored by Sayan Bhattacharya and Peter Kiss from the Theory and Foundations Research Division at Warwick, along with Thatchaphol Saranurak (University of Michigan) and David Wajc (Stanford University), has received the best paper award at SODA 2023.

Computing a maximum matching in a graph is a fundamental problem in combinatorial optimisation. The paper considers this problem in a dynamic graph, which keeps changing over time via a sequence of edge insertions and deletions. It was a decade-old open question to decide whether one can beat the performance guarantee of the simple greedy algorithm for this problem (which gives 2 approximation), in a dynamic setting. The paper answers this question in the affirmative, and provides the first efficient dynamic algorithm which can maintain a better-than 2 approximation to the size of the maximum matching in the input graph.

We are delighted to report that Dr Tom Gur (Warwick CS) and Dr Animesh Datta (Warwick Physics) have been awarded an EPSRC New Horizons on "Property Testing for Quantum Engineering". This project aims to bring together computer scientists and physicists towards the end of designing new approaches for fault-tolerant quantum computing.

From this Saturday (1 Oct to 5 Oct 2022), local residents of New Town, Kolkata, India will be able to use their mobile phones to vote for their favourite puja (a festival decoration for worshipping) as part of the annual Durga Puja festival celebration. New Town is a modern satellite city of Kolkata with about one million population. Durga Puja is one of the most important festivals in India, especially in Kolkata.

The online voting system implements a cryptographic protocol called DRE-ip, which was proposed by Dr Siamak Shahandashti and Professor Feng Hao in 2016 in an ERC-funded project. This protocol ensures that the e-voting system is end-to-end verifiable, hence giving every voter a chance to verify the tallying integrity of an election. The DRE-ip protocol was previously used in a Gateshead e-voting trial for polling station voting in 2019. This time it will be trialled for online voting, supported by a Royal Society international collaboration grant and University Policy Support Fund in collaboration with Professor Bimal Roy of the Indian Statistical Institute and the New Town Kolkata Development Authority (NKDA), West Bengel, India.

The online voting system has been developed by a group of 2021/2022 Master of Engineering (MEng) students (Horia Druliac, Matthew Bardsley, Chris Riches and Chris Dunn) in the Computer Science department as part of their MEng group project. The same group of students won the 2022 Innovation award.