FG1 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.