Researchers from the Max Planck Institute for Software Systems (MPI-SWS), the Max Planck Institute for Informatics (MPI-INF), and the Max Planck Institute for Security and Privacy (MPI-SP) have coauthored 20 papers at the LICS 2026 and ICALP 2026 conferences, two of the top conferences in theoretical computer science. LICS is the premier conference on logic in computer science and ICALP is the flagship conference of the European Association for Theoretical Computer Science.

From MPI-SWS:

1. Automata on S-adic Words. Valérie Berthé, Toghrul Karimov, and Mihir Vahanwala (ICALP, Track B)


2. Hypersequent calculi have Ackermannian upper bounds. A. R. Balasubramanian, Vitor Greati and Revantha Ramanayake (LICS)


3. Infinite-State Games with Energy Objectives Beyond Counters. Irmak Sağlam and Georg Zetzsche (ICALP, Track B)


4. On the Subspace Orbit Problem and the Simultaneous Skolem Problem. Piotr Bacik and Anton Varonka (LICS)


5. On Variable-Bounded Non-Linear Expansions of Presburger Arithmetic. Piotr Bacik, Joris Nieuwveld, Joël Ouaknine, Mihir Vahanwala, Madhavan Venkatesh and Emil Rugaard Wieser (LICS)


6. Optimally Controlling a Random Population. Hugo Gimbert, Corto Mascle, Patrick Totzke (ICALP, Track B)


7. Optimal Sequential Flows. Hugo Gimbert, Corto Mascle, Patrick Totzke (ICALP, Track A)


8. Population Protocols over Ordered Agents. Michael Blondin, Michaël Cadilhac, Benjamin Courchesne, Lucie Guillou, Corto Mascle, and Isa Vialard (ICALP, Track B)


9. The Complexity of Nested Reset Counter Systems. A. R. Balasubramanian and Franzisco Schmidt (LICS)


10. The Complexity of Downward Closures of Indexed Languages. Richard Mandel, Corto Mascle and Georg Zetzsche (LICS)

From MPI-SP:

1. Complete Relational Logic for Infinite-Dimensional Quantum Programs with Unbounded Assertions. Gilles Barthe, Minbo Gao, Jam Kabeer Ali Khan, Matthijs Muis, Ivan Renison, Keiya Sakabe, Michael Walter, Yingte Xu, Tianshi Yu and Li Zhou (LICS)

From MPI-INF:

1. A Faster Directed Single-Source Shortest Path Algorithm. Ran Duan, Xiao Mao, Xinkai Shu, Longhui Yin (ICALP, Track A)


2. Computing the (k+2)-Edge-Connected Components in k-Edge-Connected Digraphs in Subquadratic Time. Loukas Georgiadis, Evangelos Kipouridis, Evangelos Kosinas, Charis Papadopoulos, Nikos Parotsidis (ICALP, Track A)


3. Faster Algorithms for k-Orthogonal Vectors in Low Dimension. Anita Dürr, Evangelos Kipouridis, Michael Lampis, Karol Węgrzycki (ICALP, Track A)


4. Fast Decremental Tree Sums in Forests. Benjamin Aram Berendsohn, Marek Sokołowski (ICALP, Track A)


5. Improved Tree Sparsifiers in Near-Linear Time. Daniel Agassy, Dani Dorfman, Haim Kaplan (ICALP, Track A)


6. Low Rank MSO. Mikołaj Bojańczyk, Michał Pilipczuk, Wojciech Przybyszewski, Marek Sokołowski and Giannos Stamoulis (LICS)


7. Node-Weighted Triangles: Faster and Simpler. Shyan Akmal, Nick Fischer (ICALP, Track A)


8. Permutation Patterns in Streams. Benjamin Aram Berendsohn (ICALP, Track A)


9. Random Access in Grammar-Compressed Strings: Optimal Trade-Offs in Almost All Parameter Regimes. Anouk Duyster, Tomasz Kociumaka (ICALP, Track A)

 

The EATCS Award for the best theory paper at ETAPS 2026 was awarded to Isa Vialard, Joël Ouaknine and Quentin Guilmant for their paper "The value problem for weighted timed games with two clocks is undecidable", published in FoSSaCS 2026. The EATCS award is given each year to the best ETAPS papers in theoretical computer science.

The paper solves a long-standing open problem in the field of quantitative games. Weighted timed games were introduced in several works in the early 2000s, and constitute a fundamental model for formal verification and control. The key decision problems for quantitative games are the existence of winning strategies and the ‘value problem’: is the inf-sup across all pairs of Minimizer/Maximizer strategies smaller than a given rational? With three clocks, the value problem was proved undecidable in 2015. With a single clock, the problem was shown to be decidable in 2022. This paper finally closes the gap: with two clocks, both problems are shown to be undecidable using a novel and ingenious reduction, resulting in a deep contribution

MPI-SWS scientific director Joël Ouaknine was appointed as a Fellow by the European Association for Theoretical Computer Science (EATCS). Joël, who leads the “Foundations of Algorithmic Verification” research group, was appointed EATCS fellow for "fundamental contributions to the algorithmic analysis of dynamical systems and related formalisms."

The EATCS Fellows Program was established by the association in 2014 to recognize outstanding EATCS members for their scientific achievements in the field of Theoretical Computer Science.

Further Information: 

• https://eatcs.org/index.php/component/content/article/1-news/3028--eatcs-fellows-class-of-2026-named
• https://www.eatcs.org/index.php/eatcs-fellows