ÌÇÐÄTV

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 is the main conference and annual meeting of the .

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.

In total, 5 ÌÇÐÄTV papers will appear at this year's :

• Michael Benedikt, Dmitry Chistikov, and Alessio Mansutti, "",
• Sam Coy, , Peter Davies, and , "",
• Charilaos Efthymiou and Weiming Feng, "",
• Marvin Künnemann, Filip Mazowiecki, Lia Schütze, Henry Sinclair-Banks, and Karol WÄ™grzycki, "",
• Konstantinos Zampetakis and Charilaos Efthymiou, "".

This July's will be the 50th edition of the conference.