dr hab. Marcin Kozik, prof. UJ
Jednostki:
- Wydział Matematyki i Informatyki UJ
- Instytut Informatyki Analitycznej
- Katedra Algorytmiki
Habilitacja Otwarcie: 2010-05-27, Zamknięcie: 2011-01-13
Publikacje:
34.
Injective hardness condition for PCSPs, IEEE Symposium on Logic in Computer Science [LICS], (2024),
33.
Marcin Kozik, Libor Barto, Michael Pinsker, Bertalan Bodor, Antoine Mottet
Symmetries of Graphs and Structures that Fail to Interpret a Finite Thing, IEEE Symposium on Logic in Computer Science [LICS] vol. brak (2023), 1-13
32.
Libor Barto, Marcin Kozik
Combinatorial Gap Theorem and Reductions between Promise CSPs, ACM/SIAM Symposium on Discrete Algorithms [SODA], (2022), pp.1204 - 1220
31.
Libor Barto, Zarathustra Brady , Andrei Bulatov, Marcin Kozik, Dmitriy Zhuk
Minimal Taylor Algebras as a Common Framework for the Three Algebraic Approaches to the CSP, IEEE Symposium on Logic in Computer Science [LICS] vol. 1 (2021), 1-13
30.
Solving CSPs using weak local consistency, SIAM Journal on Computing vol. 50(4) (2021), 1263-1286
29.
Libor Barto, Tan Johnson, Marcin Kozik, Matthew Valeriote
Sensitive Instances of the Constraint Satisfaction Problem, International Colloquium on Automata Languages and Programming [ICALP](MAIN), (2020), 110:1-110:18
28.
Miron Ficak, Marcin Kozik, Miroslav Olsak, Szymon Stankiewicz
Dichotomy for symmetric boolean PCSPs, International Colloquium on Automata Languages and Programming [ICALP](MAIN), (2019), 57:1-57:12
27.
Victor Dalmau, Marcin Kozik, Andrei Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal
Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs, SIAM Journal on Computing vol. 48(6) (2019), 1763–1795
26.
Alexandr Kazda, Marcin Kozik, Ralph McKenzie, Matthew Moore
Absorption and directed Jónsson terms, (2018), "Don Pigozzi on Abstract Algebraic Logic", Springer
25.
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
24.
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
23.
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
22.
Weak consistency notions for all CSPs of bounded width, Proceedings of the 31st Annual Acm/ieee Symposium On Logic in Computer Science (lics'16) (2016), 633-641
21.
Libor Barto, Marcin Kozik
Robustly Solvable Constraint Satisfaction Problems, SIAM Journal on Computing vol. 45(4) (2016), 1646–1669
20.
Marcin Kozik, Joanna Ochremiak
Algebraic Properties of Valued Constraint Satisfaction Problem, Proceedings of 42nd International Colloquium, Icalp 2015 (2015), 846-858
19.
Libor Barto, Marcin Kozik, David Stanovský
Mal’tsev conditions, lack of absorption, and solvability, Algebra Universalis vol. 74 (2015), 185-206
18.
Marcin Kozik, Andrei Krokhin, Matthew Valeriote, Ross Willard
Characterizations of several Maltsev conditions, Algebra Universalis vol. 73 (2015), 205-224
17.
Libor Barto, Marcin Kozik
Constraint Satisfaction Problems Solvable by Local Consistency Methods, Journal of the ACM vol. 61 (2014), article no. 3
16.
Libor Barto, Marcin Kozik
Robust Satisfiability of Constraint Satisfaction Problems, Proceedings of the 44th Acm Symposium On Theory of Computing, Stoc'12 (2012), 931-940
15.
Libor Barto, Marcin Kozik, Ross Willard
Near unanimity constraints have bounded pathwidth duality, Proceedings of the 27th Ieee/acm Symposium On Logic in Computer Science Lics'12 (2012), 125-134
14.
Libor Barto, Marcin Kozik
Absorbing subalgebra, cyclic terms and the Constraint Satisfaction Problem, Logical Methods in Computer Science vol. 20 (2012), paper no. 7
13.
Libor Barto, Marcin Kozik
Cyclic terms for SD(V) varieties revisited, Algebra Universalis vol. 64 (2010), 137-142
12.
Libor Barto, Marcin Kozik
New conditions for Taylor varieties and CSP, Proceedings of the 25th Ieee/acm Symposium On Logic in Computer Science Lics'10 (2010), 100-109
11.
A 2EXPTIME Complete Varietal Membership Problem, SIAM Journal on Computing vol. 6 (2009), 2443-2467
10.
Libor Barto, Marcin Kozik, Todd Niven
9.
Libor Barto, Marcin Kozik
Congruence distributivity implies bounded width, SIAM Journal on Computing vol. 39 (2009), 1531-1542
8.
Libor Barto, Marcin Kozik, Miklós Maróti, Todd Niven
CSP dichotomy for special triads, Proceedings of the American Mathematical Society vol. 137 (2009), 2921-2934
7.
Libor Barto, Marcin Kozik
Constraint Satisfaction Problems of Bounded Width, Proceedings of the 50th Symposium On Foundations of Computer Science, Focs'09 (2009), 595-603
6.
Libor Barto, Marcin Kozik, Miklós Maróti, Ralph McKenzie, Todd Niven
Congruence modularity implies cyclic terms for finite algebras, Algebra Universalis vol. 61 (2009), 365-380
5.
A finite set of functions with an EXPTIME-complete composition problem, Theoretical Computer Science vol. 407 (2008), 330-341
4.
Marcin Kozik, Gábor Kun
The subdirectly irreducible algebras in the variety generated by graph algebras, Algebra Universalis vol. 58 (2008), 229-242
3.
Libor Barto, Marcin Kozik, Todd Niven
Graphs, polymorphisms and the complexity of homomorphism problems, Proceedings of the 40th Acm Symposium On Theory of Computing, Stoc'08 (2008), 789-796
2.
1.
On-line Coloring of I_s-free graphs and co-planar graphs, Discrete Mathematics and Theoretical Computer Science Proceedings vol. AF (2006), 61-68
Konferencje:
3.
The 46th International Colloquium on Automata, Languages and Programming (ICALP 2019), University of Patras i European Association for Theoretical Computer Science (EATCS), Patras, Grecja, 2019-07-08 - 2019-07-12
2.
The Constraint Satisfaction Problem: Complexity and Approximability, Schloss Dagstuhl Leibniz Center for Informatics, Dagstuhl, Niemcy, 2018-06-03 - 2018-06-08
1.
The Structure of Finite Algebras and the Constraint Satisfaction Problem, Banff International Research Station, Banff, Kanada, 2017-08-06 - 2017-08-13
Granty (realizowane po maju 2009 roku)
| Tytuł | Rola | Rozpoczęcie | Zakończenie |
|---|---|---|---|
| Topologiczne kody korekcyjne w obliczeniach kwantowych odpornych na błędy | Kierownik | 2022-10-01 | 2026-10-31 |
| "Problemy Spełnialności Więzów: poza przypadek skończony" | Kierownik | 2022-09-29 | 2026-09-28 |
| Organizacja 101 edycji konferencji Arbeitstagung Allgemeine Algebra (AAA 101) | Kierownik | 2020-11-01 | 2021-03-31 |
| Teoria algebraiczna dla CSP (złożoność obliczeniowa, aproksymacja i optymalizacja) | Kierownik | 2015-02-18 | 2019-02-17 |
| DATALOG w Problemie Spełnialności Więzów | Kierownik | 2011-12-07 | 2015-06-06 |
| Algebraiczne podejście do Problemu Spełnialności Więzów (Constraint Satisfaction Problem) | Kierownik | 2009-05-15 | 2012-05-14 |