Hi all! There are a lot of holidays in May, so we haven't seen each other in a while. This Friday, Damiano will be presenting a joint talk between our GdT and the complexités GdT. Abstract below. See you there! Morgan -------- Courriel original -------- Objet: Seminar "axe complexités": Damiano Mazza on 22/05 (joint with gdt Catégories) Date: 2026-05-18 14:19 De: Sylvain Perifel <perifel@lipn.univ-paris13.fr> À: "lipn.tous@lipn.univ-paris13.fr" <lipn.tous@lipn.univ-paris13.fr> Cc: hoffbeck@math.univ-paris13.fr Dear all, The next "Axe complexités seminar" is joint with the "Groupe de travail Catégories" and will take place next Friday at 10:30. Note the *unusual date and time*. When: Friday, May 22, at 10:30 Where: room B107 Speaker: Damiano Mazza (LIPN) Title: Constraint satisfaction problems: between complexity and categorical algebra (see abstract below) As usual, the talk is intended for a wide audience. In case you want to attend online, the BBB room will be at https://bbb.lipn.univ-paris13.fr/b/mus-djh-bjk-ljz For past talk videos, as well as future planned talks, please see the website: https://lipn.univ-paris13.fr/~mustafa/AxeComplexites/ See you on Friday! Nabil & Sylvain ---------- Speaker: Damiano Mazza Title: Constraint satisfaction problems: between complexity and categorical algebra Abstract: Constraint satisfaction problems (CSP) are a vast class of problems naturally arising in practical context, especially combinatorial optimization. In the early 90s, Feder and Vardi conjectured that CSPs enjoy a dichotomy: a CSP either admits a polynomial-time algorithm or can be proved to be NP-complete. Building on the work of several people spanning about 25 years, Bulatov and Zhuk indpendently proved the conjecture in 2017, and Feder and Vardi were awarded the Church Prize for starting this research area. The theory of CSPs heavily relies on tools from universal algebra. Very recently, Hadek, Jakl and Opršal found a categorical reformulation which neatly reorganizes and generalizes this theory. I will present my understanding of Hadek, Jakl and Opršal's paper (which has been accepted at LICS 2026) and I will introduce CSPs and their theory trying to keep as much as possible the parallel between the usual, combinatorial definitions and the categorical ones, and hopefully manage to give an idea of the proof of the hardness part of the dichotomy theorem, i.e., that "hard" CSPs are necessarily NP-complete.