Best Student Paper Award at MFCS
The International Symposium on Mathematical Foundations of Computer Science (MFCS) is a long-running, high-quality venue for original research across the breadth of theoretical computer science. The 50th edition took place 25–29 August 2025 in Warsaw, Poland. The programme covered core areas of theoretical computer science and related topics: algorithms and data structures, computational complexity, automata and formal languages, logic, verification, cryptography and security, distributed and parallel computing, network algorithms, and quantum computing.
Anton Varonka, a PhD student in the Doctoral College “Logical Methods in Computer Science” at TU Wien Informatics (co-funded by the EU’s Marie Skłodowska-Curie Actions), supervised by Prof. Laura Kovács, won the Best Student Paper Award at MFCS 2025 for “On Piecewise Affine Reachability with Bellman Operators,” co-authored with Kazuki Watanabe (NII). The paper examines the reachability problem for piecewise affine maps. These maps can exhibit complex dynamics, and reachability is known to be undecidable even in two dimensions. The authors focus on the subclass of Bellman operators arising from Markov decision processes and establish new decidability results. In any dimension, reachability is decidable if (i) the target vector is not a fixed point of the operator or (ii) the source and target are comparable in the componentwise order. In two dimensions, reachability for Bellman operators is always decidable. These results refine the boundary between undecidability and decidability and link foundational theory to applications in AI and dynamic systems.