The wonderland of reflections

L Barto, J Opršal, M Pinsker - Israel Journal of Mathematics, 2018 - Springer
A fundamental fact for the algebraic theory of constraint satisfaction problems (CSPs) over a
fixed template is that pp-interpretations between at most countable ω-categorical relational …

Schaefer's theorem for graphs

M Bodirsky, M Pinsker - Journal of the ACM (JACM), 2015 - dl.acm.org
Schaefer's theorem is a complexity classification result for so-called Boolean constraint
satisfaction problems: it states that every Boolean constraint satisfaction problem is either …

The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems

L Barto, M Pinsker - Proceedings of the 31st Annual ACM/IEEE …, 2016 - dl.acm.org
We prove that an ω-categorical core structure primitively positively interprets all finite
structures with parameters if and only if some stabilizer of its polymorphism clone has a …

Projective clone homomorphisms

M Bodirsky, M Pinsker, A Pongrácz - The Journal of Symbolic Logic, 2021 - cambridge.org
It is known that a countable-categorical structure interprets all finite structures primitively
positively if and only if its polymorphism clone maps to the clone of projections on a two …

Topology is irrelevant (in a dichotomy conjecture for infinite domain constraint satisfaction problems)

L Barto, M Pinsker - SIAM Journal on Computing, 2020 - SIAM
The tractability conjecture for finite domain constraint satisfaction problems (CSPs) stated
that such CSPs are solvable in polynomial time whenever there is no natural reduction, in …

The equivalence of two dichotomy conjectures for infinite domain constraint satisfaction problems

L Barto, M Kompatscher, M Olšák… - 2017 32nd Annual …, 2017 - ieeexplore.ieee.org
There exist two conjectures for constraint satisfaction problems (CSPs) of reducts of finitely
bounded homogeneous structures: the first one states that tractability of the CSP of such a …

Constraint satisfaction problems for reducts of homogeneous graphs

M Bodirsky, B Martin, M Pinsker, A Pongrácz - SIAM Journal on Computing, 2019 - SIAM
For n≧3, let (H_n,E) denote the n th Henson graph, ie, the unique countable homogeneous
graph with exactly those finite graphs as induced subgraphs that do not embed the complete …

Smooth approximations and CSPs over finitely bounded homogeneous structures

A Mottet, M Pinsker - Proceedings of the 37th Annual ACM/IEEE …, 2022 - dl.acm.org
We introduce the novel machinery of smooth approximations, and apply it to confirm the
CSP dichotomy conjecture for first-order reducts of the random tournament, and to give new …

The complexity of phylogeny constraint satisfaction problems

M Bodirsky, P Jonsson, TV Pham - ACM Transactions on Computational …, 2017 - dl.acm.org
We systematically study the computational complexity of a broad class of computational
problems in phylogenetic reconstruction. The class contains, for example, the rooted triple …

Complexity classification transfer for CSPs via algebraic products

M Bodirsky, P Jonsson, B Martin, A Mottet… - SIAM Journal on …, 2024 - SIAM
We study the complexity of infinite-domain constraint satisfaction problems (CSPs): our basic
setting is that a complexity classification for the CSPs of first-order expansions of a structure …