Showing cs.CCShow all
2 papers · 1 filter
cs.CC2024
The Complexity of Promise Constraint Satisfaction Problem Seen from the Other Side
Kristina Asimi, Libor Barto, Victor Dalmau
We introduce the framework of the left-hand side restricted promise constraint satisfaction problem, which includes problems like approximating clique number of a graph. We study t…
cs.CC2024
The Rise of Plurimorphisms: Algebraic Approach to Approximation
Libor Barto, Silvia Butti, Alexandr Kazda +2
Following the success of the so-called algebraic approach to the study of decision constraint satisfaction problems (CSPs), exact optimization of valued CSPs, and most recently pro…