Data Science News
Best Paper Award at SODA 2023
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.
Ian Mertz joins the department as a Research Fellow
Ian Mertz completed his PhD at the University of Toronto in 2022 under the supervision of Toniann Pitassi, with stints at the Simons Institute for the Theory of Computing (UC Berkeley) and at the Institute for Advanced Study in Princeton.
Ian's primary research area is computational complexity theory. His interests at the moment include catalytic computing, lifting theorems, arithmetic circuit complexity, and proof complexity.
Latest two academic promotions
We are happy to announce two promotions in the department.
Dr Fayyaz Minhas has been promoted to Associate Professor from 1 July 2022.
Dr Rossella Suma has been promoted to Assistant Professor from 1 August 2022.
Many congratulations to our colleagues for all their achievements!