Algebra Seminar talk
2018-10-12 (10:15)
Antoine Mottet (Charles University, Prague)
A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP
Abstract:
The logic MMSNP is a restricted fragment of existential second-order logic
which allows to express many interesting queries in graph theory and finite
model theory. The logic was introduced by Feder and Vardi who showed that
every MMSNP sentence is computationally equivalent to a finite-domain
constraint satisfaction problem (CSP); the involved probabilistic
reductions were derandomized by Kun using explicit constructions of
expander structures.
I will present a new proof of the reduction to finite-domain CSPs that does not rely on the results of Kun. This new approach relies on universal algebra and recent Ramsey-theoretic results. Based on joint work with Manuel Bodirsky.