72 citations · 72 across the 2 of their papers we have counts for
2 papers
cs.CC2012★ 72 cited
Essential Convexity and Complexity of Semi-Algebraic Constraints
Manuel Bodirsky, Peter Jonsson, Timo von Oertzen
Let Γbe a structure with a finite relational signature and a first-order definition in (R;*,+) with parameters from R, that is, a relational structure over the real numbers where a…
cs.LO2010
Horn versus full first-order: complexity dichotomies in algebraic constraint satisfaction
Manuel Bodirsky, Peter Jonsson, Timo von Oertzen
We study techniques for deciding the computational complexity of infinite-domain constraint satisfaction problems. For certain fundamental algebraic structures Delta, we prove defi…