Publikacje

• The sorrows of a smooth digraph: the first hardness criterion for infinite directed graph-colouring problems - 2025 IEEE Symposium on Logic in Computer Science [LICS], (2025), Brunar Johanna, Marcin Kozik, Tomáš Nagy, Michael Pinsker
• Classical simulation of quantum CSP strategies - 2025 IEEE Symposium on Logic in Computer Science [LICS], (2025), 372-388 Demian Banakh, Ciardo Lorenzo, Marcin Kozik, Jan Tułowiecki
• Unifying the three algebraic approaches to the CSP via minimal Taylor algebras - 2024
  Theoretics 3 (2024), Libor Barto, Zarathustra Brady, Andrei Bulatov, Marcin Kozik, Dmitriy Zhuk
• 1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise - 2024 IEEE Symposium on Logic in Computer Science [LICS], (2024), Article No.: 24, Pages 1 - 12 Ciardo Lorenzo, Marcin Kozik, Andrei Krokhin, Vesa Nakajima Tamio, Zivny Stanislav
• Injective hardness condition for PCSPs - 2024 IEEE Symposium on Logic in Computer Science [LICS], (2024), article number 8 Demian Banakh, Marcin Kozik
• Symmetries of Graphs and Structures that Fail to Interpret a Finite Thing - 2023 IEEE Symposium on Logic in Computer Science [LICS] brak (2023), 1-13 Libor Barto, Bertalan Bodor, Marcin Kozik, Antoine Mottet, Michael Pinsker
• Combinatorial Gap Theorem and Reductions between Promise CSPs - 2022 ACM/SIAM Symposium on Discrete Algorithms [SODA], (2022), pp.1204 - 1220 Libor Barto, Marcin Kozik
• Minimal Taylor Algebras as a Common Framework for the Three Algebraic Approaches to the CSP - 2021 IEEE Symposium on Logic in Computer Science [LICS] 1 (2021), 1-13 Libor Barto, Zarathustra Brady, Andrei Bulatov, Marcin Kozik, Dmitriy Zhuk
• Solving CSPs using weak local consistency - 2021
  SIAM Journal on Computing 50(4) (2021), 1263-1286 Marcin Kozik
• Sensitive Instances of the Constraint Satisfaction Problem - 2020 International Colloquium on Automata Languages and Programming [ICALP](MAIN), (2020), 110:1-110:18 Libor Barto, Tan Johnson, Marcin Kozik, Matthew Valeriote
• Dichotomy for symmetric boolean PCSPs - 2019 International Colloquium on Automata Languages and Programming [ICALP](MAIN), (2019), 57:1-57:12 Miron Ficak, Marcin Kozik, Miroslav Olsak, Szymon Stankiewicz
• Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs - 2019
  SIAM Journal on Computing 48(6) (2019), 1763–1795 Victor Dalmau, Marcin Kozik, Andrei Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal
• Absorption and directed Jónsson terms - 2018 (2018), "Don Pigozzi on Abstract Algebraic Logic", Springer Alexandr Kazda, Marcin Kozik, Ralph McKenzie, Matthew Moore
• Absorption in Universal Algebra and CSP - 2017 (2017), "The Constraint Satisfaction Problem: Complexity and Approximability", Schloss Dagstuhl – Leibniz-Zentrum für Informatik Libor Barto, Marcin Kozik
• Robust algorithms with polynomial loss for near-unanimity CSPs - 2017
  Proceedings of the 28th Annual Acm-siam Symposium On Discrete Algorithms Soda'17 (2017), 340-357 Victor Dalmau, Marcin Kozik, Andrei Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal
• The subpower membership problem for semigroups - 2016
  International Journal of Algebra and Computation 26 (2016), 1435-1451 Andrei Bulatov, Marcin Kozik, Peter Mayr, Markus Steindl
• Weak consistency notions for all CSPs of bounded width - 2016
  Proceedings of the 31st Annual Acm/ieee Symposium On Logic in Computer Science (lics'16) (2016), 633-641 Marcin Kozik
• Robustly Solvable Constraint Satisfaction Problems - 2016
  SIAM Journal on Computing 45(4) (2016), 1646–1669 Libor Barto, Marcin Kozik
• Algebraic Properties of Valued Constraint Satisfaction Problem - 2015
  Proceedings of 42nd International Colloquium, Icalp 2015 (2015), 846-858 Marcin Kozik, Joanna Ochremiak
• Mal’tsev conditions, lack of absorption, and solvability - 2015
  Algebra Universalis 74 (2015), 185-206 Libor Barto, Marcin Kozik, David Stanovský
• Characterizations of several Maltsev conditions - 2015
  Algebra Universalis 73 (2015), 205-224 Marcin Kozik, Andrei Krokhin, Matthew Valeriote, Ross Willard
• Constraint Satisfaction Problems Solvable by Local Consistency Methods - 2014
  Journal of the ACM 61 (2014), article no. 3 Libor Barto, Marcin Kozik
• Robust Satisfiability of Constraint Satisfaction Problems - 2012
  Proceedings of the 44th Acm Symposium On Theory of Computing, Stoc'12 (2012), 931-940 Libor Barto, Marcin Kozik
• Near unanimity constraints have bounded pathwidth duality - 2012
  Proceedings of the 27th Ieee/acm Symposium On Logic in Computer Science Lics'12 (2012), 125-134 Libor Barto, Marcin Kozik, Ross Willard
• Absorbing subalgebra, cyclic terms and the Constraint Satisfaction Problem - 2012
  Logical Methods in Computer Science 20 (2012), paper no. 7 Libor Barto, Marcin Kozik
• Cyclic terms for SD(V) varieties revisited - 2010
  Algebra Universalis 64 (2010), 137-142 Libor Barto, Marcin Kozik
• New conditions for Taylor varieties and CSP - 2010
  Proceedings of the 25th Ieee/acm Symposium On Logic in Computer Science Lics'10 (2010), 100-109 Libor Barto, Marcin Kozik
• A 2EXPTIME Complete Varietal Membership Problem - 2009
  SIAM Journal on Computing 6 (2009), 2443-2467 Marcin Kozik
• The CSP dichotomy holds for digraphs with no sources and no sinks (a positive answer to a conjecture of Bang-Jensen and Hell) - 2009
  SIAM Journal on Computing 38 (2009), 1782-1802 Libor Barto, Marcin Kozik, Todd Niven
• Congruence distributivity implies bounded width - 2009
  SIAM Journal on Computing 39 (2009), 1531-1542 Libor Barto, Marcin Kozik
• CSP dichotomy for special triads - 2009
  Proceedings of the American Mathematical Society 137 (2009), 2921-2934 Libor Barto, Marcin Kozik, Miklós Maróti, Todd Niven
• Constraint Satisfaction Problems of Bounded Width - 2009
  Proceedings of the 50th Symposium On Foundations of Computer Science, Focs'09 (2009), 595-603 Libor Barto, Marcin Kozik
• Congruence modularity implies cyclic terms for finite algebras - 2009
  Algebra Universalis 61 (2009), 365-380 Libor Barto, Marcin Kozik, Miklós Maróti, Ralph McKenzie, Todd Niven
• A finite set of functions with an EXPTIME-complete composition problem - 2008
  Theoretical Computer Science 407 (2008), 330-341 Marcin Kozik
• The subdirectly irreducible algebras in the variety generated by graph algebras - 2008
  Algebra Universalis 58 (2008), 229-242 Marcin Kozik, Gábor Kun
• Graphs, polymorphisms and the complexity of homomorphism problems - 2008
  Proceedings of the 40th Acm Symposium On Theory of Computing, Stoc'08 (2008), 789-796 Libor Barto, Marcin Kozik, Todd Niven
• Computationally and algebraically complex finite algebra membership problems - 2007
  International Journal of Algebra and Computation 17 (2007), 1635-1666] Marcin Kozik
• On-line Coloring of I_s-free graphs and co-planar graphs - 2006
  Discrete Mathematics and Theoretical Computer Science Proceedings AF (2006), 61-68 Iwona Cieślik-Bielecka, Marcin Kozik, Piotr Micek