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
February 24 | Jan Hladký (Prague) | Inhomogeneous random 2SAT |
March 3 | Soichiro Fuiji (Brno) | Hom complexes of graph homomorphisms and square-free graphs |
March 10 | Zoltán Vidnyánszky (Elte) | Infinite versions of the CSP Dichotomy theorem |
March 24 | Max Hadek (Prague) | A new perspective on constraint satisfaction: The wonderland of adjunctions |
March 31 | Jakub Rydval (TU Wien) | Constraint satisfaction problems with infinite domains |
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.
Past terms
Spring 2021: Special Seminar – part of Round the World Relay in Combinatorics, where a number of seminars and groups around the world were getting together. Each site hosted a talk, and everyone was welcome.
Fall 2020: ITI Online Seminar – a one-semester online venue for presenting current research in discrete mathematics and theoretical computer science in the Czech Republic.