A paperLink opens in a new window co-authored by Arpan MukhopadhyayLink opens in a new window has received the Best Paper Award at ACM Mobihoc 2024Link opens in a new window. Mobihoc is a premier international conference on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing. The other authors in the paper are Samira Ghanbarian (uWaterloo), Ravi R. Mazumdar (uWaterloo), and Fabrice Guillemin (Orange Labs, France).

The paper addresses the problem of optimally allocating processors to parallelisable tasks having arbitrary concave speed-up functions. In general, determining the optimal number of processors to allocate to each task in an online fashion is a hard problem since allocating too many processors to one job will make those processors unavailable to other jobs whereas allocating too few processors will result in a small speed-up for the job. The paper proposes a simple randomised algorithm for determining the optimal number of processors to allocate to each job without requiring preemption (or repacking). It shows that the proposed algorithm is asymptotically optimal as the number of processors becomes large (which is often the case in modern clouds) and is also robust to variations in the job size distribution. This is the first time such an algorithm has been found in the literature.

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).

Eight papers authored by Computer Science researchers from Warwick have been accepted for publication at the 38th Conference on Neural Information Processing Systems, the leading international venue for machine learning research, which will be held on 10-15 December 2024 in Vancouver, British Columbia, Canada:

• Generating Origin-Destination Matrices in Neural Spatial Interaction Models, by Ioannis Zachos, Mark Girolami, and Theodoros Damoulas
• Interventionally Consistent Surrogates for Complex Simulation Models, by Joel Dyer, Nicholas Bishop, Yorgos Felekis, Fabio Massimo Zennaro, Ani Calinescu, Theodoros Damoulas, and Michael Wooldridge
• Learning the Expected Core of Strictly Convex Stochastic Cooperative Games, by Phuong Nam Tran, The Anh Ta, Shuqing Shi, Debmalya Mandal, Yali Du, and Long Tran-Thanh
• Physics-Informed Variational State-Space Gaussian Processes, by Oliver Hamelijnck, Arno Solin, and Theodoros Damoulas
• SARAD: Spatial Association-Aware Anomaly Detection and Diagnosis for Multivariate Time Series, by Zhihao Dai, Ligang He, Shuanghua Yang, and Matthew Leeke
• Symmetric Linear Bandits with Hidden Symmetry, by Phuong Nam Tran, The Anh Ta, Debmalya Mandal, and Long Tran-Thanh
• The Effectiveness of Surprisingly Popular Voting with Partial Preferences, by Hadi Hosseini, Debmalya Mandal, and Amrit Puhan
• What makes unlearning hard and what to do about it, by Kairan Zhao, Meghdad Kurmanji, George-Octavian Bărbulescu, Eleni Triantafillou, and Peter Triantafillou

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.

Toby Flynn, PhD student in the department's High-Performance and Scientific Computing group, supervised by Prof. Gihan Mudalige together with Dr. Robert Manson-Sawko at IBM Research UK received the best paper award at the 38th IEEE International Parallel and Distributed Processing Symposium (IPDPS 2024) last week in San Francisco US. IPDPS is one of the most prominent and high ranking conferences in parallel and distributed computing, now in its 38th year.

The paper titled "Performance-Portable Multiphase Flow Solutions with Discontinuous Galerkin Methods", details the development of a new performance portable solver workflow using Discontinuous Galerkin (DG) methods for developing multiphase flow simulations based on the OP2 domain-specific language. Results demonstrate scaling on both CPU and GPU systems including UK's national supercomputer, ARCHER2 at EPCC Edinburgh and the European Petascale Supercomputer, LUMI hosted by CSC Finland. The work is a collaboration with IBM Research UK supported by an iCASE award funded jointly by IBM and EPSRC.

The paper pre-print is available here.

The Department of Computer Science is hosting the alumni reunion conference on March 22nd - bringing together current and past students, along with academics and researchers to enjoy a day of talks and demonstrations.

Mustafa Yasir, a former Warwick Department of Computer Science student who graduated in Summer 2023, wrote up and presented an academic paper on the work carried out as part of his third year project. The paper was accepted to the 3rd Annual Workshop on Graph Learning Benchmarks at KDD 2023, and was presented in California by Mustafa.

Mustafa's third year project idea, supervised by Dr Long Tran-Thanh and titled 'Extending the Graph Generation Models of GraphWorld', started whilst he was interning at Google last summer. Mustafa contacted some researchers at the company working in the Graph ML space, to ask for any relevant project ideas. He bumped into a team who had just published GraphWorld: a tool to change the way Graph Neural Networks are benchmarked, by creating synthetic graph datasets through graph generation models – as opposed to using real-world datasets that are limited in their generalisability and present a major issue facing the field of Graph Learning.

However, since GraphWorld only used a single graph generation model in this process, Mustafa integrated two additional models with the system, ran large-scale GNN benchmarking experiments with these models and published his code to Google’s official GraphWorld repository. The project provides a significant advancement to researchers across the field looking to benchmark models and guide the development of new architectures.

Dr Long Tran-Thanh commented:

What Mustafa and the GraphWorld team has been working on is very important for the machine learning and AI research communities. In particular, there has been a vocal criticism against the whole field that most models are trained on the same public datasets (e.g., ImageNet, MNIST, etc), therefore are not diverse enough. One way to mitigate this issue is to generate realistically looking synthetic data. This need is especially of importance in within the graph learning community. GraphWorld’s aim is to address this exact problem by creating a powerful and convenient tool that can generate a diverse set of graphs, ranging from large social network-style graphs to molecule-inspired ones. Joining this project with the Google researchers is a huge opportunity for Warwick students to participate in a very impactful project.