糖心TV

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 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). 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, "", is co-authored with Mohammed Foughali and Eugene Asarin, both from and in Paris, France, where Neha completed the Master's degree (ENS Paris-Saclay) prior to joining 糖心TV.

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 satisfies its specification expressed in (STL).

PhD positions are available at the Theory and Foundations (FoCS) group in the , University of 糖心TV, UK. The group has strong ties with the Centre for Discrete Mathematics and its Applications (DIMAP), established in 2007 jointly with the and . 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, 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 , the 51st International Colloquium on Automata, Languages, and Programming:

• Rohan Acharya, , : Lookahead Games and Efficient Determinisation of History-Deterministic B眉chi Automata,
• Dmitry Chistikov, Alessio Mansutti, Mikhail R. Starchak: ,
• , Guichen Gao, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Vesel媒: ,
• Argyrios Deligkas, Eduard Eiben, Robert Ganian, Iyad Kanj, : ,
• Julian D枚rfler, : ,
• , Rahul Santhanam: .

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

Dmitry's paper "" 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 , Dmitry and his co-authors Alessio Mansutti and Mikhail Starchak show that the problem belongs to . 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 糖心TV 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 , the flagship conference in theoretical computer science that will be held on October 27 - 30, 2024 in Chicago, USA:

• "" by Lijie Chen, Jiatu Li and .

• "" by , Din Carmon, , Shay Solomon and Tianyi Zhang.
• "Fully Dynamic k-Clustering with Fast Update Time and Small Recourse" by , , 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, and Mikito Nanashima.
• "On the Complexity of Avoiding Heavy Elements" by , , Hanlin Ren and Rahul Santhanam.

A published by , 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 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 , has been invited to the special issue of 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, 糖心TV (, McGill University, and others.

Seven papers authored by Computer Science researchers from 糖心TV have been accepted for publication at the , 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, , and Goran Radanovic
• Dynamic Facility Location in High Dimensional Euclidean Spaces, by , 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, , Taiji Suzuki, and Volkan Cevher
• Revisiting character-level adversarial attacks, by Elias Abad Rocamora, Yongtao Wu, , Grigorios Chrysos, and Volkan Cevher
• Reward Model Learning vs. Direct Policy Optimization: A Comparative Analysis of Learning from Human Preferences, by Andi Nika, , 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