We are delighted to announce that Peter Kiss, a PhD student in the Theory and Foundations Research Division, has won the Best Student Paper Award at the Innovations in Theoretical Computer Science (ITCS) 2022 conference for his single-author paper on "Deterministic Dynamic Matching in Worst-Case Update Time". Computing a maximum matching in a graph is one of the most fundamental problems in design and analysis of algorithms. The paper makes important progress on this problem in a setting where the input graph is changing over time via a sequence updates, and one wishes to maintain a large matching efficiently in such a dynamic graph. Along the way, the paper develops a general purpose technique for converting any dynamic algorithm with amortised update time into one with worst-case update time, provided the initial algorithm is able to handle a more general form of batch updates.

We are very pleased to welcome Alex Dixon, a new Teaching Fellow in our department.

Alex first joined the department in 2013, originally as an undergraduate student, and then as a postgraduate student studying automata theory. He has a keen interest in logic, automata, and functional programming.

We look forward to having him in the team!

We are delighted to report that Dr Ramanujan Sridharan (PI) from the Theory and Foundations (FoCS) research theme at the Department of Computer Science and Professor Graham Cormode (Co-I, affiliated with FoCS) have been awarded an EPSRC Standard Research Grant, "New Horizons in Multivariate Preprocessing (MULTIPROCESS)".

This 4-year £540K project aims to advance the theory of preprocessing by designing novel multivariate preprocessing algorithms and extending their scope to high-impact big data paradigms such as streaming algorithms.