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.

Six papers co-authored by DIMAP and Theory and Foundations researchers were presented earlier in July at ICALP 2024, the 51st International Colloquium on Automata, Languages, and Programming:

• Rohan Acharya, Marcin Jurdzinski, Aditya Prakash: Lookahead Games and Efficient Determinisation of History-Deterministic Büchi Automata,
• Dmitry Chistikov, Alessio Mansutti, Mikhail R. Starchak: Integer Linear-Exponential Programming in NP by Quantifier Elimination,
• Artur Czumaj, Guichen Gao, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý: Fully-Scalable MPC Algorithms for Clustering in High Dimension,
• Argyrios Deligkas, Eduard Eiben, Robert Ganian, Iyad Kanj, M. S. Ramanujan: Parameterized Algorithms for Coordinated Motion Planning: Minimizing Energy,
• Julian Dörfler, Christian Ikenmeyer: Functional Closure Properties of Finite ℕ-Weighted Automata,
• Zhenjian Lu, Rahul Santhanam: Impagliazzo's Worlds Through the Lens of Conditional Kolmogorov Complexity.

ICALP is the main conference and annual meeting of the European Association for Theoretical Computer Science (EATCS). This year's ICALP took place in Tallinn, Estonia, on the 8th to 12th of July 2024.

Dmitry's paper "Integer Linear-Exponential Programming in NP by Quantifier Elimination" won the Best Paper Award of ICALP's Track B, which is a flagship research meeting on Automata, Logic, Semantics, and Theory of Programming. The paper studies the following problem: given a system of linear equations and constraints of the form y=2^x, does it have a solution over the natural numbers? By using and extending a method that generalises Gaussian elimination, Dmitry and his co-authors Alessio Mansutti and Mikhail Starchak show that the problem belongs to the complexity class NP. This result provides a way to efficiently certify the existence of a solution, even if all solutions are very big (towers of exponentials).

This is the second time in a row that this award goes to a Warwick paper: Henry Sinclair-Banks, a DIMAP PhD student, was an awardee in 2023.

Six papers from the Theory and Foundations Research Group and the Centre for Discrete Mathematics and Its Applications (DIMAP) have been accepted to the 65th IEEE Symposium on Foundations of Computer Science (FOCS 2024), the flagship conference in theoretical computer science that will be held on October 27 - 30, 2024 in Chicago, USA:

• "Reverse Mathematics of Complexity Lower Bounds" by Lijie Chen, Jiatu Li and Igor C. Oliveira.

• "Faster (Δ+1)-Edge Coloring: Breaking the m n^1/2 Time Barrier" by Sayan Bhattacharya, Din Carmon, Martin Costa, Shay Solomon and Tianyi Zhang.
• "Fully Dynamic k-Clustering with Fast Update Time and Small Recourse" by Sayan Bhattacharya, Martin Costa, Naveen Garg, Silvio Lattanzi and Nikos Parotsidis.
• "The Tractability Border of Reachability in Simple Vector Addition Systems with States" by Dmitry Chistikov, Wojciech Czerwiński, Łukasz Orlikowski, Filip Mazowiecki, Henry Sinclair-Banks and Karol Węgrzycki.

• "Optimal Coding Theorems for Randomized Kolmogorov Complexity and Its Applications" by Shuichi Hirahara, Zhenjian Lu and Mikito Nanashima.
• "On the Complexity of Avoiding Heavy Elements" by Zhenjian Lu, Igor C. Oliveira, Hanlin Ren and Rahul Santhanam.

A recent paperLink opens in a new window published by Dr. Ian MertzLink opens in a new window, a postdoctoral researcher in the Theory and Foundations (FoCS)Link opens in a new window research group and the Centre for Discrete Mathematics and its Applications (DIMAP)Link opens in a new window, has disproved a longstanding conjecture on the limitations of space-bounded computation.

For many years it had been believed that a function, known as Tree Evaluation, would be the key to separating two fundamental classes of problems: those computable quickly (P), and those computable in low space (L). Mertz, along with James CookLink opens in a new window of Toronto, builds on their earlier work to show a low-space algorithm for Tree Evaluation, thus refuting this belief. In particular, their technique has attracted attention for shedding new light on the power of space-bounded computation, suggesting novel approaches to age-old questions in complexity theory. They show that space can be used in surprising ways, with the same memory serving many simultaneous purposes.

The paper, which Mertz will present at the 56th Annual ACM Symposium on the Theory of Computing (STOC 2024)Link opens in a new window, has been invited to the special issue of SIAM Journal on Computing (SICOMP)Link opens in a new window for the conference. STOC is the main conference of the Association of Computing Machinery (ACM) and one of the two premier venues for theoretical computer science, with only the top results being invited for publication in the special issue.

Mertz has also presented this work at many venues, including the Institute for Advanced Study (IAS), Columbia University, Oxford University, Warwick (Online Complexity Seminar)Link opens in a new window, McGill University, and others.

Seven papers authored by Computer Science researchers from Warwick have been accepted for publication at the 41st International Conference on Machine Learning, one of the top three global venues for machine learning research, which will be held on 21-27 July 2024 in Vienna, Austria:

• Agent-Specific Effects: A Causal Effect Propagation Analysis in Multi-Agent MDPs, by Stelios Triantafyllou, Aleksa Sukovic, Debmalya Mandal, and Goran Radanovic
• Dynamic Facility Location in High Dimensional Euclidean Spaces, by Sayan Bhattacharya, Gramoz Goranci, Shaofeng Jiang, Yi Qian, and Yubo Zhang (Accepted as a spotlight, among the top 13 percent of all accepted papers)
• High-Dimensional Kernel Methods under Covariate Shift: Data-Dependent Implicit Regularization, by Yihang Chen, Fanghui Liu, Taiji Suzuki, and Volkan Cevher
• Revisiting character-level adversarial attacks, by Elias Abad Rocamora, Yongtao Wu, Fanghui Liu, Grigorios Chrysos, and Volkan Cevher
• Reward Model Learning vs. Direct Policy Optimization: A Comparative Analysis of Learning from Human Preferences, by Andi Nika, Debmalya Mandal, Parameswaran Kamalaruban, Georgios Tzannetos, Goran Radanovic, and Adish Singla
• To Each (Textual Sequence) Its Own: Improving Memorized-Data Unlearning in Large Language Models, by George-Octavian Bărbulescu and Peter Triantafillou
• Towards Neural Architecture Search through Hierarchical Generative Modeling, by Lichuan Xiang, Łukasz Dudziak, Mohamed Abdelfattah, Abhinav Mehrotra, Nicholas Lane, and Hongkai Wen

We are happy to announce four promotions in the department:

• Dr Charilaos Efthymiou has been promoted to Associate Professor
• Dr Igor Carboni Oliveira has been promoted to Associate Professor
• Dr Hongkai Wen has been promoted to Professor
• Dr Weiren Yu has been promoted to Associate Professor

Many congratulations to our colleagues for all their achievements!

On this recent article in the Quanta magazine, Alex Dixon, who wrote in Haskell the first solver for the problem, commented:

For the past 50 years, Vector Addition Systems—a simple but powerful computational model—have been a topic of great interest in theoretical CS. The reachability problem in that model asks whether we can get from some configuration to another.

The problem sounds relatively easy on a first glance, and an exponential lower bound held firm for over 40 years. Work by excellent theoreticians, including familiar names from Warwick DCS, finally closed the difficulty of the problem in 2021, concluding that it is very, very difficult indeed.