Hi!
No GdT is planned for this morning. If you want to use the room to
discuss something, it is booked anyway.
Best,
Morgan
1
0
GdT demain
by Groupe de travail catégories
05 Jun '26
05 Jun '26
Bonjour!
Comme prévu, il y aura demain matin en B107 la continuation de l'exposé
de Damiano. d'il y a deux semaines.
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.
Pour rappel, le BBB sera celui de l'axe Complexités:
https://bbb.lipn.univ-paris13.fr/b/mus-djh-bjk-ljz
---
Hi!
Tomorrow Damiano will continue his talk on CSPs. Details above.
See you tomorrow,
Morgan
