109 citations · 149 across the 9 of their papers we have counts for
13 papers
Constant-factor approximation of MinCostCSP with a conservative majority polymorphism
Marcin Kozik, Stanislav Živný
For a relational structure A, the Minimum Cost Constraint Satisfaction Problem is the following problem denoted by MinCostCSP(A): Given an instance of CSP(A) with rational costs on…
Symmetries of structures that fail to interpret something finite
Libor Barto, Bertalan Bodor, Marcin Kozik +2
We investigate structural implications arising from the condition that a given directed graph does not interpret, in the sense of primitive positive interpretation with parameters…
Combinatorial Gap Theorem and Reductions between Promise CSPs
Libor Barto, Marcin Kozik
A value of a CSP instance is typically defined as a fraction of constraints that can be simultaneously met. We propose an alternative definition of a value of an instance and show…
Unifying the Three Algebraic Approaches to the CSP via Minimal Taylor Algebras
Libor Barto, Zarathustra Brady, Andrei Bulatov +2
This paper focuses on the algebraic theory underlying the study of the complexity and the algorithms for the Constraint Satisfaction Problem (CSP). We unify, simplify, and extend p…
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…
Dichotomy for symmetric Boolean PCSPs
Miron Ficak, Marcin Kozik, Miroslav Olsak +1
A PCSP is a combination of two CSPs defined by two similar templates; the computational question is to distinguish a YES instance of the first one from a NO instance of the second.…