Teoria algebraiczna dla CSP (złożoność obliczeniowa, aproksymacja i optymalizacja)
2014/13/B/ST6/01812
Słowa kluczowe
Deskryptory
- ST6_4: Metody formalne, teoretyczne podstawy informatyki w tym informatyka teoretyczna
- ST6_6: Algorytmika, algorytmy równoległe, rozproszone i sieciowe, algorytmiczna teoria gier
- ST1_18: Zastosowania matematyki w innych naukach
Panel
ST6 – Informatyka i technologie informacyjne: technologie i systemy informacyjne, informatyka, obliczenia naukowe, systemy inteligentne
Jednostka realizująca
Uniwersytet Jagielloński, Wydział Matematyki i Informatyki
woj. małopolskie
Kierownik projektu (z jednostki realizującej)
Liczba wykonawców projektu: 3
Konkurs
OPUS 7 – ogłoszony 2014-03-17
- Przyznana kwota
- 486 920 PLN
- Rozpoczęcie projektu
- 2015-02-18
- Zakończenie projektu
- 2019-02-17
- Planowany czas trwania projektu
- 48 miesięcy (z wniosku)
- Status projektu
- Projekt rozliczony
Zakupiona aparatura
- Laptop. Za kwotę 8 000 PLN
Dane z raportu końcowego/rocznego
Publikacje w czasopismach (6)
-
Loop conditions for strongly connected graphs
- Autorzy:
- Miroslav Olsak
- Czasopismo:
- International Journal of Algebra and Computation (rok: 2020, tom: 30(03), strony: 467-499), Wydawca: WORLD SCIENTIFIC PUBL
- Status:
- Opublikowana
- DOI:
- 10.1142/S0218196720500083 – link do publikacji
-
Local loop lemma
- Autorzy:
- Miroslav Olsak
- Czasopismo:
- Algebra Universalis (rok: 2020, tom: 81, strony: article no. 14), Wydawca: Springer
- Status:
- Opublikowana
- DOI:
- 10.1007/s00012-020-0644-y – link do publikacji
-
Robust algorithms with polynomial loss for near-unanimity CSPs
- Autorzy:
- Victor Dalmau, Marcin Kozik, Andrzej Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal
- Czasopismo:
- SIAM Journal on Computing (rok: 2019, tom: 48(6), strony: 1763–1795), Wydawca: SIAM Publications
- Status:
- Opublikowana
- DOI:
- 10.1137/18M1163932 – link do publikacji
-
Taylor's modularity conjecture and related problems for idempotent varieties
- Autorzy:
- Jakub Oprsal
- Czasopismo:
- Order (rok: 2018, tom: 35, strony: 433-460), Wydawca: Springer
- Status:
- Opublikowana
- DOI:
- 10.1007/s11083-017-9441-4 – link do publikacji
-
The subpower membership problem for semigroups
- Autorzy:
- Andrei Bulatov, Marcin Kozik, Peter Mayr, Markus Steindl
- Czasopismo:
- International Journal of Algebra and Computation (rok: 2016, tom: 26, strony: 1435-1451), Wydawca: World Scientific
- Status:
- Opublikowana
- DOI:
- 10.1142/S0218196716500612 – link do publikacji
-
Solving CSPs using weak local consistency
- Autorzy:
- Marcin Kozik
- Status:
- Przyjęta do publikacji
Teksty w publikacjach pokonferencyjnych (3)
-
Dichotomy for symmetric Boolean PCSPs
- Autorzy:
- Miron Ficak, Marcin Kozik, Miroslav Olsak, Szymon Stankiewicz
- Konferencja:
- 46th International Colloquium on Automata, Languages and Programming (ICALP 2019) (rok: 2019, strony: 57:1-57:12), Wydawca: Leibniz International Proceedings in Informatics
- Data:
- konferencja 8-9.06.2019
- Status:
- Opublikowana
- DOI:
- link do publikacji
-
Sensitive Instances of the Constraint Satisfaction Problem
- Autorzy:
- Libor Barto, Marcin Kozik, Johnson Tan, Matt Valeriote
- Konferencja:
- 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) (rok: 2020, strony: 110:1-110:18), Wydawca: Schloss Dagstuhl--Leibniz-Zentrum f{u}r Informatik
- Data:
- konferencja 8-11.07.2020
- Status:
- Opublikowana
- DOI:
- link do publikacji
-
Robust algorithms with polynomial loss for near-unanimity CSPs
- Autorzy:
- Victor Dalmau, Marcin Kozik, Andrei Krokhin, Konstantin Makarychev, Yuri Makarychev, Jakub Oprsal
- Konferencja:
- Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (rok: 2016, strony: 340-357), Wydawca: SIAM
- Data:
- konferencja 10-12.01.2016
- Status:
- Opublikowana
- DOI:
- link do publikacji
Publikacje książkowe (1)
-
Absorption in Universal Algebra and CSP
- Autorzy:
- Libor Barto, Marcin Kozik
- Książka:
- The Constraint Satisfaction Problem: Complexity and Approximability (rok: 2017, tom: 7, strony: 45-77), Wydawca: Shloss Dagstuhl
- Status:
- Opublikowana
- DOI:
- link do publikacji