109 citations · 149 across the 9 of their papers we have counts for
Showing 2016Show all
3 papers · 1 filter
cs.DS2016
Robust algorithms with polynomial loss for near-unanimity CSPs
Víctor Dalmau, Marcin Kozik, Andrei Krokhin +3
An instance of the Constraint Satisfaction Problem (CSP) is given by a family of constraints on overlapping sets of variables, and the goal is to assign values from a fixed domain…
cs.CC2016★ 16 cited
Weaker consistency notions for all the CSPs of bounded width
Marcin Kozik
The characterization of all the Constraint Satisfaction Problems of bounded width, proposed by Feder and Vardi [SICOMP'98], was confirmed in [Bulatov'09] and independently in [FOCS…
math.GR2016
The subpower membership problem for semigroups
Andrei Bulatov, Marcin Kozik, Peter Mayr +1
Fix a finite semigroup and let be tuples in a direct power . The subpower membership problem (SMP) asks whether can be generated by $a_1,\ldots,a_k…