Showing cs.LOShow all
3 papers · 1 filter
cs.LO2020
Sensitive instances of the Constraint Satisfaction Problem
Libor Barto, Marcin Kozik, Johnson Tan +1
We investigate the impact of modifying the constraining relations of a Constraint Satisfaction Problem (CSP) instance, with a fixed template, on the set of solutions of the instanc…
cs.LO2019
Topology is irrelevant (in a dichotomy conjecture for infinite domain constraint satisfaction problems)
Libor Barto, Michael Pinsker
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,…
cs.LO2016
The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction Problems
Libor Barto, Michael Pinsker
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…