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 takes place on Monday at 2PM term time in Room C226a in the building of the Faculty of Informatics on a (roughly) weekly schedule.

Spring 2025 – schedule overview

Speakers

Upcoming

Jan Hladký : Inhomogeneous random 2SAT

Monday, February 24, 11:00, room C325

Random k-SAT is a standard model of randomly generated Boolean formulas. This model is extremely challenging to analyze (in particular, asymptotic almost sure satisfiability) for k > 2, while it remains relatively simple for k = 2. In recent joint work with Petr Savický, we introduce an inhomogeneous variant of random 2-SAT. The inhomogeneity is generated by a two-variable function in a manner similar to how Bollobás, Janson, and Riordan generalize Erdős–Rényi random graphs. In particular, we identify a certain spectral parameter of the model that determines its asymptotic almost sure satisfiability or unsatisfiability.

Soichiro Fuiji : Hom complexes of graph homomorphisms and square-free graphs

Monday, March 3, 14:00, room C226a

The Hom complex Hom(G, H) is a certain polyhedral complex associated with a pair of (undirected, finite, and simple) graphs G and H, whose vertices correspond to the graph homomorphisms from G to H. Hom complexes have been applied to the graph coloring problem, and are also related to the more recent topic of combinatorial reconfiguration. In this talk, I will begin with the basics of Hom complexes and explain our recent result determining the homotopy type of (each connected component of) Hom(G, H) when H is square-free, meaning that it does not contain the 4-cycle graph as a subgraph. Although it is known that the homotopy type of Hom(G, H) can be quite complicated in general, for a connected G and a square-free H, we show that each connected component of Hom(G, H) is homotopy equivalent to a wedge sum of circles. (Based on joint work with Kei Kimura and Yuta Nozaki.)

Zoltán Vidnyánszky : Infinite versions of the CSP Dichotomy theorem

Monday, March 10, 14:00, room C226a

The CSP dichotomy theorem of Bulatov and Zhuk is a celebrated result in computer science: it states that for a given finite structure H, the problem of deciding whether a structure G admits a homomorphism to H is either easy (in P) or very hard (NP-complete). In this talk, I will provide an overview of this theorem and discuss two extensions to infinite domains—one in the Borel and one in the choiceless setting.

Max Hadek : A new perspective on constraint satisfaction: The wonderland of adjunctions

Monday, March 24, 14:00, room C226a

The so-called algebraic approach to constraint satisfaction problems has been a prevalent method of the study of complexity of these problems since the early 2000s, and it provides the foundation of the famous dichotomy proofs of Bulatov and Zhuk. We discuss a new, top-down perspective on the main theorems of the algebraic approach, unveiling its connections to category theory and algebraic topology.

Jakub Rydval : Constraint satisfaction problems with infinite domains

Monday, March 31, 14:00, room C226a

The Bodirsky-Pinsker conjecture extends the CSP dichotomy theorem of Bulatov and Zhuk to certain highly symmetric infinite structures. In this talk, I motivate the conjecture and provide an overview of the current state of the infinite-domain CSP. We discuss recent progress, challenges, and connections to other related fields.

Tomáš Jakl : Game comonads and dense graph parameters

Monday, May 26, 14:00, room A321

Model comparison games are an important tool for expressibility results in database theory and finite model theory. In recent years we have seen a growing number of examples of model comparison games (such as pebble games or Ehrenfreucht-Fraisse games) being encoded semantically, as comonads on the class of graphs or relational structures. Apart from the connections with logic, game comonads also express a range of important parameters in finite model theory and combinatorics, such as tree-width and tree-depth.

In this talk I will give motivations and a brief introduction to game comonads and discuss the current progress towards capturing dense graph parameters such as modular width and clique width.