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
Upcoming 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) | Constraint satisfaction problems with infinite domains |
March 24 | Max Hadek (Prague) |
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 : Constraint satisfaction problems with infinite domains
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.
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.