A paper co-authored by Matthias C. Caro has been featured on the cover of PRX Quantum. PRX Quantum is a premier journal for quantum information science and technology research. The work was a collaboration with Haimeng Zhao (Caltech & Tsinghua), Laura Lewis (Caltech & Google), Ishaan Kannan (Caltech), Yihui Quek (Harvard & MIT) and Hsin-Yuan Huang (Caltech, Google & MIT).

Characterizing a quantum system by learning its state or unitary evolution is a key tool in developing quantum devices, with applications in practical quantum machine learning, benchmarking, and error mitigation. However, in general, this task requires exponentially many resources. Prior knowledge is required to circumvent this exponential bottleneck. The paper pinpoints the complexity for learning states and unitaries that can be implemented by quantum circuits with a bounded number of gates, a broad setting that is topical for current quantum technologies. When measuring efficiency with respect to the number of accesses to the unknown quantum state or unitary, the paper presents and implements algorithms that are provably optimally efficient. Thereby, this work establishes the equivalence between the complexity of learning quantum states or unitaries and the complexity of creating them. However, it also shows that the data processing necessarily requires exponential computation time under reasonable cryptographic assumptions.

We are happy to announce that an academic from our department, Dr Sayan Bhattacharya, is among the winners of ERC Consolidator Grants 2024. According to the European Research Council: "These grants, totalling €678 million, aim to support outstanding scientists and scholars as they establish their independent research teams and develop their most promising scientific ideas. The funding is provided through the EU's Horizon Europe programme."

Sayan Bhattacharya has been awarded a €2million ERC Consolidator grant for a 5-year project entitled "Towards a Dynamic Algorithms Centric Theory of Linear Programming" (DYNALP). The project aims to build a new theory exploring the interplay between two key concepts, Linear Programming and Dynamic Algorithms, which, in turn, will pave the way towards attacking outstanding open questions in the field of Theoretical Computer Science.

In the 2024 round, this was the only project from the United Kingdom that was awarded an ERC Consolidator Grant in Computer Science and Informatics (PE6 panel). The press release contains more information about the ERC funding programme.

We are delighted to announce that Martin Costa, a PhD student at the Theory and Foundations research division, has received a highly competitive Google PhD Fellowship for his work on designing clustering algorithms for dynamic datasets. The Fellowship comes in the form of an unrestricted gift from Google, of 60,000 USD per year, for up to two years. Under the category of "Algorithms and Theory", besides Martin only two other PhD students in Europe (from University of Cambridge and ETH Zurich) received a Google PhD Fellowship this year. Many congratulations to Martin for this achievement!

Neha Rino, a PhD student in the Theory and Foundations group in the Department of Computer Science and a member of the Cyber Security group at WMG, has won an Oded Maler award at FORMATS 2024.

The Oded Maler award is a distinction presented for the best paper of the International Conference on Formal Modeling and Analysis of Timed Systems (FORMATS). This year's edition of the conference was held in September in Calgary, Canada, jointly with QEST (International Conference on Quantitative Evaluation of SysTems) as a common research forum dedicated to quantitative modelling, analysis, and verification.

Neha's paper, "Efficiently Computable Distance-Based Robustness for a Practical Fragment of STL", is co-authored with Mohammed Foughali and Eugene Asarin, both from Université Paris Cité and IRIF in Paris, France, where Neha completed the Master's degree (ENS Paris-Saclay) prior to joining Warwick.

Neha's paper contributes to the research framework of quantitative monitoring, which is the analysis of individual executions of systems which yields numerical output (real numbers), rather than binary yes/no. The paper formulates and solves, by an efficient algorithm, a new problem of this kind: computing a real number that characterises to which extent the given execution of a real-time system satisfies its specification expressed in Signal Temporal Logic (STL).

PhD positions are available at the Theory and Foundations (FoCS) group in the Department of Computer Science, University of Warwick, UK. The group has strong ties with the Centre for Discrete Mathematics and its Applications (DIMAP), established in 2007 jointly with the Warwick Mathematics Institute and Warwick Business School. Together with DIMAP, the group is one of the leading theory groups in Europe, with regular publications in top international conferences and journals in theoretical computer science.

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.