Algebra Seminar talk

2018-11-09 (13:30)
Alexandr Kazda (Charles University Prague)
Wonderland of Reflections for Weighted Clones

Abstract:
Weighted clones describe the complexity of valued constraint satisfaction problem (VCSP) with fixed constraint language. While it is already known which languages of constraints give rise to polynomial solvable or NP-hard VCSP problems (Kolmogorov, Krokhin, Rolínek, 2015) and there is a theory of varieties for weighted algebras (Kozik, Ochremiak, 2015), the algebraic side of VCSP is still not fully explored. We will show that reflections of weighted clones give rise to computational reductions between VCSP languages.