Description
2026. március 16. (hétfő), 10:15-11:15,
Rényi Intézet, Nagyterem (+Zoom)
Abstract:
The Constraint Satisfaction Problem, or CSP for short, over a relational structure B (called the template structure) is the decision problem where we are given a finite structure A with the same signature as B and we need to decide whether there exists a homomorphism from A to B. According to the famous result of Bulatov and Zhuk we know that CSPs over finite template structures exhibit a complexity dichotomy: they are all in P or NP-complete. Following this result, it is natural to ask when and how this dichotomy can be generalized for infinite template structures. A currently standing conjecture in this direction is due to Bodirsky and Pinsker which states that the same complexity dichotomy holds for first-order reducts of finitely bounded homogeneous structures.
In my talk I will give a brief introduction to some of the main techniques and results used in the study of CSPs putting a special emphasis on the ones with infinite templates. In this endeavour I might touch on some topics in model theory as well.
https://us06web.zoom.us/j/88170589772?pwd=alKno1wb6whK00eKns7wzgezSDg3vi.1
Meeting ID: 881 7058 9772
Passcode: 512995