Algebraic theory for CSP (tractability, approximation and optimization)
2014/13/B/ST6/01812
Keywords
Descriptors
- 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 – Computer science and informatics: informatics and information systems, computer science, scientific computing, intelligent systems
Host institution
Uniwersytet Jagielloński, Wydział Matematyki i Informatyki
Voivodeship: małopolskie
Principal investigator (from the host institution)
Number of co-investigators in the project: 3
Call
OPUS 7 – announced on 2014-03-17
- Amount awarded
- 486 920 PLN
- Project start date
- 2015-02-18
- Project end date
- 2019-02-17
- Project duration
- 48 months (the same as in the proposal)
- Project status
- Project settled
Equipment purchased [PL]
- Laptop. Cost: 8 000 PLN
Information in the final report
Publication in academic press/journals (6)
-
Loop conditions for strongly connected graphs
- Authors:
- Miroslav Olsak
- Academic press:
- International Journal of Algebra and Computation (year: 2020, volume: 30(03), pages: 467-499), Publisher: WORLD SCIENTIFIC PUBL
- Status:
- Published
- DOI:
- 10.1142/S0218196720500083 – link to the publication
-
Local loop lemma
- Authors:
- Miroslav Olsak
- Academic press:
- Algebra Universalis (year: 2020, volume: 81, pages: article no. 14), Publisher: Springer
- Status:
- Published
- DOI:
- 10.1007/s00012-020-0644-y – link to the publication
-
Robust algorithms with polynomial loss for near-unanimity CSPs
- Authors:
- Victor Dalmau, Marcin Kozik, Andrzej Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal
- Academic press:
- SIAM Journal on Computing (year: 2019, volume: 48(6), pages: 1763–1795), Publisher: SIAM Publications
- Status:
- Published
- DOI:
- 10.1137/18M1163932 – link to the publication
-
Taylor's modularity conjecture and related problems for idempotent varieties
- Authors:
- Jakub Oprsal
- Academic press:
- Order (year: 2018, volume: 35, pages: 433-460), Publisher: Springer
- Status:
- Published
- DOI:
- 10.1007/s11083-017-9441-4 – link to the publication
-
The subpower membership problem for semigroups
- Authors:
- Andrei Bulatov, Marcin Kozik, Peter Mayr, Markus Steindl
- Academic press:
- International Journal of Algebra and Computation (year: 2016, volume: 26, pages: 1435-1451), Publisher: World Scientific
- Status:
- Published
- DOI:
- 10.1142/S0218196716500612 – link to the publication
-
Solving CSPs using weak local consistency
- Authors:
- Marcin Kozik
- Status:
- Accepted for publication
Articles in post-conference publications (3)
-
Dichotomy for symmetric Boolean PCSPs
- Authors:
- Miron Ficak, Marcin Kozik, Miroslav Olsak, Szymon Stankiewicz
- Conference:
- 46th International Colloquium on Automata, Languages and Programming (ICALP 2019) (year: 2019, pages: 57:1-57:12), Publisher: Leibniz International Proceedings in Informatics
- Date:
- conference 8-9.06.2019
- Status:
- Published
- DOI:
- link to the publication
-
Sensitive Instances of the Constraint Satisfaction Problem
- Authors:
- Libor Barto, Marcin Kozik, Johnson Tan, Matt Valeriote
- Conference:
- 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) (year: 2020, pages: 110:1-110:18), Publisher: Schloss Dagstuhl--Leibniz-Zentrum f{u}r Informatik
- Date:
- conference 8-11.07.2020
- Status:
- Published
- DOI:
- link to the publication
-
Robust algorithms with polynomial loss for near-unanimity CSPs
- Authors:
- Victor Dalmau, Marcin Kozik, Andrei Krokhin, Konstantin Makarychev, Yuri Makarychev, Jakub Oprsal
- Conference:
- Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (year: 2016, pages: 340-357), Publisher: SIAM
- Date:
- conference 10-12.01.2016
- Status:
- Published
- DOI:
- link to the publication
Book publications / chapters in book publications (1)
-
Absorption in Universal Algebra and CSP
- Authors:
- Libor Barto, Marcin Kozik
- Book:
- The Constraint Satisfaction Problem: Complexity and Approximability (year: 2017, volume: 7, pages: 45-77), Publisher: Shloss Dagstuhl
- Status:
- Published
- DOI:
- link to the publication