Teoria algebraiczna dla CSP (złożoność obliczeniowa, aproksymacja i optymalizacja)

Instytucja Finansująca / Przyznający: NCN

Tytuł: Teoria algebraiczna dla CSP (złożoność obliczeniowa, aproksymacja i optymalizacja)

Kierownik: Marcin Kozik

Rozpoczęcie: 2015-02-18

Zakończenie: 2019-02-17

Uwagi: Opus 7


Publikacje
Andrei Bulatov, Marcin Kozik, Peter Mayr, Markus Steindl, The subpower membership problem for semigroups, International Journal of Algebra and Computation vol. 26 (2016), 1435-1451
Victor Dalmau, Marcin Kozik, Andrei Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal, Robust algorithms with polynomial loss for near-unanimity CSPs, Proceedings of the 28th Annual Acm-siam Symposium On Discrete Algorithms Soda'17 (2017), 340-357
Libor Barto, Marcin Kozik, Absorption in Universal Algebra and CSP, (2017), "The Constraint Satisfaction Problem: Complexity and Approximability", Schloss Dagstuhl – Leibniz-Zentrum für Informatik