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
To be clear, this will be happening on Friday 05/06 at 10:30am :) M Le 2026-06-04 13:31, Groupe de travail catégories a écrit :
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 _______________________________________________ Categories mailing list Categories@lipn.univ-paris13.fr https://lipn.univ-paris13.fr/listes-lipn/listinfo/categories
bbb.lipn.univ-paris13.fr/b/rog/vao-uwm-s2j Le 04/06/2026 à 13:32, Groupe de travail catégories a écrit :
To be clear, this will be happening on Friday 05/06 at 10:30am :) M
Le 2026-06-04 13:31, Groupe de travail catégories a écrit :
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 _______________________________________________ Categories mailing list Categories@lipn.univ-paris13.fr https://lipn.univ-paris13.fr/listes-lipn/listinfo/categories
Categories mailing list Categories@lipn.univ-paris13.fr https://lipn.univ-paris13.fr/listes-lipn/listinfo/categories
participants (1)
-
Groupe de travail catégories