72 citations · 130 across the 27 of their papers we have counts for
3 papers · 1 filter
Computational Short Cuts in Infinite Domain Constraint Satisfaction
Peter Jonsson, Victor Lagerkvist, Sebastian Ordyniak
A backdoor in a finite-domain CSP instance is a set of variables where each possible instantiation moves the instance into a polynomial-time solvable class. Backdoors have found ma…
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…
Almost Consistent Systems of Linear Equations
Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak +2
Checking whether a system of linear equations is consistent is a basic computational problem with ubiquitous applications. When dealing with inconsistent systems, one may seek an a…