Speaker
Adam Ó Conghaile, Quantinuum
Title
Shaefer Via Topology - Cohomology for CSPs on Boolean Domains
Abstract
Shaefer’s dichotomy theorem for Boolean domains was the first in a (growing) list of theorems which classify all tractable cases for certain constraint satisfaction problems. In this work in progress we claim that all tractable cases in Shaefer’s theorem are solved by a single topological algorithm (cohomological k-consistency) and we outline several approaches to reproving Shaefer’s theorem (and its generalisation to all CSPs) from a topological standpoint.
