Computer Science News
Best Student Paper Award at European Symposium on Algorithms
We are delighted to announce that Peter Kiss, a PhD student in the Theory and Foundations Research Division, has received the best student paper award at European Symposium on Algorithms (ESA) 2023, for his joint work with Joakim Bilkstad for the paper: "Incremental (1-eps)-approximate dynamic matching in O(poly(1/eps)) update time". The paper considers the problem of maintaining a large matching in a graph that is undergoing a sequence of edge insertions. They present an algorithm for this fundamental problem in dynamic graph algorithms, which has near-optimal approximation ratio and an update time that does not grow at all with the size of the input and is also polynomial in 1/\eps (the error parameter). In addition, their approach is simpler than previous algorithms on the same problem that achieved weaker guarantees.
5 papers accepted to FOCS 2023
Five papers from the Theory and Foundations (FoCS) Research Group and the Centre for Discrete Mathematics and its Applications (DIMAP) have been accepted to the 64th IEEE Symposium on Foundations of Computer Science (FOCS 2023), the IEEE flagship conference in theoretical computer science that will be held on November 6 - 9, 2023 in Santa Cruz, California, USA:
- "Chasing positive bodies" by Sayan Bhattacharya, Niv Buchbinder, Roie Levin, and Thatchaphol Saranurak.
- "Dynamic (1+epsilon)-approximate matching size in truly sublinear update time" by Sayan Bhattacharya, Peter Kiss, and Thatchaphol Saranurak.
- "Polynomial-time pseudodeterministic construction of primes" by Lijie Chen, Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, and Rahul Santhanam.
- "Approximating edit distance in the fully dynamic model" by Tomasz Kociumaka, Anish Mukherjee, and Barna Saha.
- "Traversing combinatorial 0/1-polytopes via optimization" by Arturo Merino and Torsten Mütze.
Best Paper Award and 5 papers at the 50th ICALP conference
Henry Sinclair-Banks, a PhD student in the the Theory and Foundations (FoCS) Research Group and the Centre for Discrete Mathematics and its Applications (DIMAP), has won a Best Paper Award at ICALP 2023, the 50th EATCS International Colloquium on Automata, Languages and Programming. ICALP is the main conference and annual meeting of the European Association for Theoretical Computer Science (EATCS).
Henry's paper, co-authored with researchers from Germany and Poland: Marvin Künnemann, Filip Mazowiecki, Lia Schütze, and Karol Węgrzycki, addresses the coverability problem in vector addition systems (VASS), a well-known model of concurrent systems. Coverability is an algorithmic problem for the verification of "safety properties": whether the system always avoids a set of bad states. Henry and his co-authors determine how much time is required to solve this problem in the worst case. They develop an algorithm that improves upon the state of the art that has stood for forty years. They also prove that, in several settings, it is impossible to decide coverability substantially faster, unless there is also a faster algorithm for a classic problem such as Boolean satisfiability (SAT) and finding cycles of fixed length in graphs.


- Michael Benedikt, Dmitry Chistikov, and Alessio Mansutti, "The complexity of Presburger arithmetic with power or powers",
- Sam Coy, Artur Czumaj, Peter Davies, and Gopinath Mishra, "Optimal (degree+1)-coloring in congested clique",
- Charilaos Efthymiou and Weiming Feng, "On the mixing time of Glauber dynamics for the hard-core and related models on G(n,d/n)",
- Marvin Künnemann, Filip Mazowiecki, Lia Schütze, Henry Sinclair-Banks, and Karol Węgrzycki, "Coverability in VASS revisited: Improving Rackoff's bound to obtain conditional optimality",
- Konstantinos Zampetakis and Charilaos Efthymiou, "Broadcasting with random matrices".
This July's ICALP will be the 50th edition of the conference.
Latest academic promotions
We are happy to announce five promotions in the department, with effect from 1st August 2023.
- Dr James Archbold has been promoted to Associate Professor (Teaching Focussed)
- Dr Richard Kirk has been promoted to Assistant Professor (Teaching Focussed)
- Dr Claire Rocks has been promoted to Reader (Teaching Focussed)
- Dr Ian Saunders has been promoted to Associate Professor (Teaching Focussed)
- Dr Sathya Subramanian has been promoted to Assistant Professor (Research Focussed)
Many congratulations to our colleagues for all their achievements!
Promotion to Assistant Professor
We are happy to share the news that Dr Alex Dixon has been promoted to the position of Assistant Professor, effective from 1 May 2023. Alex joined our department as a Teaching Fellow in September 2021, while still completing his PhD research. Despite juggling both roles, he has made significant contributions to the department's activities. Many congratulations to Alex for his accomplishments in completing his PhD research and for earning this well-deserved promotion.
Cambridge-Oxford-Warwick Quantum Computing Project
An EPSRC Robust and Reliable Quantum Computing Grant will be awarded to Anuj Dawar (Cambridge), Tom Gur (Warwick), Tom Melham (Oxford), and Sergii Strelchuk (Cambridge). The project sets out to explore the role of symmetry and structure in quantum computation, with applications to classical verification and simulation of quantum computation.
In addition, the project aims to strengthen and create new connections and collaborations between Cambridge, Oxford, and Warwick in the field of Quantum Computing (building on existing initiatives such as the Cambridge-Warwick Quantum Colloquium) and establish new partnerships with Warwick Quantum.
5+ papers accepted to STOC 2023



Several papers from the Theory and Foundations (FoCS) Research Group and the Centre for Discrete Mathematics and its Applications (DIMAP) have been accepted to the 55th ACM SIGACT Symposium on Theory of Computing (STOC 2023), the ACM flagship conference in theoretical computer science that will be held on June 20-23, 2023 in Orlando, Florida, USA:
- "Kneser graphs are Hamiltonian" by Arturo Merino, Torsten Mütze, and Namrata.
- "A duality between one-way functions and average-case symmetry of information" by Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, and Igor C. Oliveira.
- "Unprovability of strong complexity lower bounds in bounded arithmetic" by Jiatu Li and Igor C. Oliveira.
- "Sublinear algorithms for (1.5+ϵ)-approximate matching" by Sayan Bhattacharya, Peter Kiss, and Thatchaphol Saranurak.
- "Towards the Erdős-Gallai cycle decomposition conjecture" by Matija Bucic and Richard Montgomery.
Further, there are two more accepted papers autored by Shuichi Hirahara, who was affiliated with the department and the FoCS group during the submission time, in Autumn 2022:
- "Capturing one-way functions via NP-hardness of meta-complexity" by Shuichi Hirahara.
- "Hardness self-amplification: Simplified, optimized, and unified" by Shuichi Hirahara and Nobutaka Shimizu.