Seminar on Foundations of Computing

This research seminar provides a venue for presenting research results concerning algorithm design, discrete mathematics, formal methods, logic and related areas of theoretical computer science. The seminar is jointly organized by the research laboratories DIMEA, FORMELA, and LIVE. The seminar builds on the FMDSA seminar organized by the FORMELA laboratory in the past.

Time and place

The seminar usually takes place on Monday at 2PM term time in Room C123 in the building of the Faculty of Informatics on a (roughly) weekly schedule.

Spring 2026 – schedule overview

Speakers

2.2.	Marta Grobelna (TU Munich)	Stopping Criteria for Value Iteration on Concurrent Stochastic Reachability and Safety Games
2.3.	Ronen Wdowinski (TU Graz)	Reconfigurability and topological variations of Hall's theorem
9.3.	Stefanie Mohr (Corvolution)	From University to Industry: Machine Learning for Sleep and Apnea Detection
16.3.	Roman Feller (TU Wien)	Decidability of Interpretability

Upcoming Speakers

23.3.	Tomáš Nagy (MUNI)
30.3.	Gaurav Kucheriya (Charles university)
20.4.	Raju Gupta (SAV Bratislava)
4.5.	Ashwin Bhaskar
11.5.	Johanna Brunar

Marta Grobelna : Stopping Criteria for Value Iteration on Concurrent Stochastic Reachability and Safety Games

Monday, February 2, 14:00, room C117

We consider two-player zero-sum concurrent stochastic games (CSGs) played on graphs with reachability and safety objectives. These include degenerate classes such as Markov decision processes or turn-based stochastic games, which can be solved by linear or quadratic programming; however, in practice, value iteration (VI) outperforms the other approaches and is the most implemented method. Similarly, for CSGs, this practical performance makes VI an attractive alternative to the standard theoretical solution via the existential theory of reals. VI starts with an under-approximation of the sought values for each state and iteratively updates them, traditionally terminating once two consecutive approximations are ϵ-close. However, this stopping criterion lacks guarantees on the precision of the approximation, which is the goal of this work. We provide bounded (a.k.a. interval) VI for CSGs: it complements standard VI with a converging sequence of over-approximations and terminates once the over- and under-approximations are ϵ-close.

Ronen Wdowinski : Reconfigurability and topological variations of Hall's theorem

Monday, March 2, 14:00, room C123

Hall's theorem allows one to deduce the existence of a complete matching in a bipartite graph, or equivalently a transversal in a set system. For proving the existence of more complicated combinatorial objects, a powerful topological extension of Hall's theorem has been developed by Aharoni, Berger, Haxell, and Meshulam.

We show that these topological methods can be used to deduce more information about the solution spaces associated with the respective combinatorial objects, in particular when these solution spaces are connected (as reconfiguration graphs). Applications of our work include (often best-possible) sufficient conditions for the reconfigurability of combinatorial objects such as independent transversals in graphs, matchings in bipartite hypergraphs, and geometric configurations associated with the colorful Helly, colorful Carathéodory, and Tverberg theorems.

Stefanie Mohr : From University to Industry: Machine Learning for Sleep and Apnea Detection

Monday, March 9, 14:00, room C123

In this talk, I describe my transition from academic research to applied machine learning in a small health-tech company. I outline how data science operates in a regulated product environment, where reliability, validation, and deployment constraints shape technical decisions. The central example is a sleep phase and apnea detection project based on ECG-derived signals and HRV features. I present the current modeling approaches, experimental results, and practical challenges. The goal is to share insights from industry practice and invite discussion on methodological improvements.

Roman Feller : Decidability of Interpretability

Monday, March 16, 14:00, room C123

The Bodirsky-Pinsker conjecture asserts a P vs. NP-complete dichotomy for the computational complexity of Constraint Satisfaction Problems (CSPs) of first-order reducts of finitely bounded homogeneous structures. Prominently, two structures in the scope of the conjecture have log-space equivalent CSPs if they are pp-bi-interpretable, or equivalently, if their polymorphism clones are topologically isomorphic. The latter gives rise to the algebraic approach which regards structures with topologically isomorphic polymorphism clones as equivalent and seeks to identify structural reasons for hardness or tractability in topological clones.

In this talk I will introduce all the above mentioned notions and then demonstrate that the equivalence relation of pp-bi-interpretability underlying this approach is reasonable: Namely, I will show that it is decidable under mild conditions on the templates; this improves results of Bodirsky, Pinsker and Tsankov on the decidability of equality of polymorphism clones. Finally, I will also sketch that this equivalence relation is of lowest possible complexity from the perspective of descriptive set theory gathering further evidence for its reasonability. This is a joint work with Michael Pinsker.