6 citations · 8 across the 25 of their papers we have counts for
Showing 2019Show all
3 papers · 1 filter
cs.LO2019
Hardness of Network Satisfaction for Relation Algebras with Normal Representations
Manuel Bodirsky, Simon Knäuer
We study the computational complexity of the general network satisfaction problem for a finite relation algebra with a normal representation . If contains a non-trivial…
math.RA2019
Two-element structures modulo primitive positive constructability
Manuel Bodirsky, Albert Vucaj
Primitive positive constructions have been introduced in recent work of Barto, Opršal, and Pinsker to study the computational complexity of constraint satisfaction problems. Let $\…
cs.LO2019
Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems)
Manuel Bodirsky, Antoine Mottet, Miroslav Olšák +3
The algebraic dichotomy conjecture for Constraint Satisfaction Problems (CSPs) of reducts of (infinite) finitely bounded homogeneous structures states that such CSPs are polynomial…