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 24Jan Hladký (Prague)Inhomogeneous random 2SAT
March 3Soichiro Fuiji (Brno)Hom complexes of graph homomorphisms and square-free graphs
March 10Zoltán Vidnyánszky (Elte)Constraint satisfaction problems with infinite domains
March 24Max 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

Fall 2024

Spring 2024

Fall 2023

Spring 2023

Fall 2022

Spring 2022

Fall 2021

Spring 2021: Special Seminarpart 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 Seminara one-semester online venue for presenting current research in discrete mathematics and theoretical computer science in the Czech Republic.

Spring 2020

Fall 2019

Spring 2019