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

Upcoming Speakers

12.10.	Žaneta Genčiová (TU Wien, CTU)	How constraints help with resilience
2.11.	Jan Bok (Charles University)
9.11.	Marek Sokolowski (Corvolution)

Žaneta Genčiová : How constraints help with resilience

Monday, October 12, 14:00, room C117

A recent research topic in database theory is the computational complexity of resilience of queries. For a fixed conjunctive query, the problem is to compute the minimal number of facts that need to be removed from a given database so that it does not satisfy the query. Thanks to the existence of homomorphism duals for conjunctive queries, resilience problems can be viewed as valued constraint satisfaction problems (VCSPs) of structures that are finite or at least finite-like (in the sense that they have an oligomorphic automorphism group). We present several complexity results for resilience problems obtained from this connection, including recent results for queries over a signature consisting of a single binary relation, so-called digraph queries. In this setting, the resilience problem for a digraph query q translates to a graph problem: given a directed multigraph G, compute the minimal number of edges to be removed so that G does not satisfy q. We show that the resilience problem for a digraph query is always in P or NP-complete. This talk is based on joint work with Manuel Bodirsky and Carsten Lutz.