72 citations · 320 across the 78 of their papers we have counts for
4 papers · 1 filter
Complexity Classification Transfer for CSPs via Algebraic Products
Manuel Bodirsky, Peter Jonsson, Barnaby Martin +2
We study the complexity of infinite-domain constraint satisfaction problems: our basic setting is that a complexity classification for the CSPs of first-order expansions of a struc…
Spectrahedral Shadows and Completely Positive Maps on Real Closed Fields
Manuel Bodirsky, Mario Kummer, Andreas Thom
In this article we develop new methods for exhibiting convex semialgebraic sets that are not spectrahedral shadows. We characterize when the set of nonnegative polynomials with a g…
The Smallest Hard Trees
Manuel Bodirsky, Jakub Bulín, Florian Starke +1
We find an orientation of a tree with 20 vertices such that the corresponding fixed-template constraint satisfaction problem (CSP) is NP-complete, and prove that for every orientat…
Asymptotic Theories of Classes Defined by Forbidden Homomorphisms
Manuel Bodirsky, Colin Jahel
We study the first-order almost-sure theories for classes of finite structures that are specified by homomorphically forbidding a set of finite structures. If $\mathc…