Marcin Kozik

45 papers A* 16Journal 27Unranked 1
YearRankTypeTitle / Venue / Authors
2025 J jnl
1-in-3 vs. Not-All-Equal: Dichotomy of a Broken Promise.
ACM Trans. Comput. Log.
Lorenzo Ciardo, Marcin Kozik, Andrei A. Krokhin, Tamio-Vesa Nakajima, Stanislav Zivný
2025 A* conf
Classical Simulation of Quantum CSP Strategies.
LICS
Demian Banakh, Lorenzo Ciardo, Marcin Kozik, Jan Tulowiecki
2025 J jnl
Classical Simulation of Quantum CSP Strategies.
CoRR
Demian Banakh, Lorenzo Ciardo, Marcin Kozik, Jan Tulowiecki
2025 A* conf
The sorrows of a smooth digraph: the first hardness criterion for infinite directed graph-colouring problems.
LICS
Johanna Brunar, Marcin Kozik, Tomás Nagy, Michael Pinsker
2025 J jnl
The sorrows of a smooth digraph: the first hardness criterion for infinite directed graph-colouring problems.
CoRR
Johanna Brunar, Marcin Kozik, Tomás Nagy, Michael Pinsker
2024 A* conf
1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise.
LICS
Lorenzo Ciardo, Marcin Kozik, Andrei A. Krokhin, Tamio-Vesa Nakajima, Stanislav Zivný
2024 A* conf
Injective hardness condition for PCSPs.
LICS
Demian Banakh, Marcin Kozik
2024 J jnl
Injective hardness condition for PCSPs.
CoRR
Demian Banakh, Marcin Kozik
2024 J jnl
Model-checking positive equality free logic on a fixed structure (direttissima).
CoRR
Manuel Bodirsky, Marcin Kozik, Florent R. Madelaine, Barnaby Martin, Michal Wrona
2024 J jnl
Unifying the Three Algebraic Approaches to the CSP via Minimal Taylor Algebras.
TheoretiCS
Libor Barto, Zarathustra Brady, Andrei Bulatov, Marcin Kozik, Dmitriy Zhuk
2023 J jnl
On the complexity of the approximate hypergraph homomorphism problem.
CoRR
Lorenzo Ciardo, Marcin Kozik, Andrei A. Krokhin, Tamio-Vesa Nakajima, Stanislav Zivný
2023 A* conf
Symmetries of Graphs and Structures that Fail to Interpret a Finite Thing.
LICS
Libor Barto, Bertalan Bodor, Marcin Kozik, Antoine Mottet, Michael Pinsker
2023 J jnl
Symmetries of structures that fail to interpret something finite.
CoRR
Libor Barto, Bertalan Bodor, Marcin Kozik, Antoine Mottet, Michael Pinsker
2022 A* conf
Combinatorial Gap Theorem and Reductions between Promise CSPs.
SODA
Libor Barto, Marcin Kozik
2021 J jnl
Combinatorial Gap Theorem and Reductions between Promise CSPs.
CoRR
Libor Barto, Marcin Kozik
2021 A* conf
Minimal Taylor Algebras as a Common Framework for the Three Algebraic Approaches to the CSP.
LICS
Libor Barto, Zarathustra Brady, Andrei Bulatov, Marcin Kozik, Dmitriy Zhuk
2021 J jnl
Minimal Taylor Algebras as a Common Framework for the Three Algebraic Approaches to the CSP.
CoRR
Libor Barto, Zarathustra Brady, Andrei Bulatov, Marcin Kozik, Dmitriy Zhuk
2021 J jnl
Solving CSPs Using Weak Local Consistency.
SIAM J. Comput.
Marcin Kozik
2020 A* conf
Sensitive Instances of the Constraint Satisfaction Problem.
ICALP
Libor Barto, Marcin Kozik, Johnson Tan, Matt Valeriote
2020 J jnl
Sensitive instances of the Constraint Satisfaction Problem.
CoRR
Libor Barto, Marcin Kozik, Johnson Tan, Matt Valeriote
2019 A* conf
Dichotomy for Symmetric Boolean PCSPs.
ICALP
Miron Ficak, Marcin Kozik, Miroslav Olsák, Szymon Stankiewicz
2019 J jnl
Dichotomy for symmetric Boolean PCSPs.
CoRR
Miron Ficak, Marcin Kozik, Miroslav Olsák, Szymon Stankiewicz
2019 J jnl
Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs.
SIAM J. Comput.
Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal
2017 — ch.
Absorption in Universal Algebra and CSP.
The Constraint Satisfaction Problem
Libor Barto, Marcin Kozik
2017 A* conf
Robust algorithms with polynomial loss for near-unanimity CSPs.
SODA
Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal
2016 J jnl
Robust algorithms with polynomial loss for near-unanimity CSPs.
CoRR
Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal
2016 J jnl
Robustly Solvable Constraint Satisfaction Problems.
SIAM J. Comput.
Libor Barto, Marcin Kozik
2016 J jnl
The subpower membership problem for semigroups.
Int. J. Algebra Comput.
Andrei Bulatov, Marcin Kozik, Peter Mayr, Markus Steindl
2016 A* conf
Weak consistency notions for all the CSPs of bounded width.
LICS
Marcin Kozik
2016 J jnl
Weaker consistency notions for all the CSPs of bounded width.
CoRR
Marcin Kozik
2015 — conf
Algebraic Properties of Valued Constraint Satisfaction Problem.
ICALP (1)
Marcin Kozik, Joanna Ochremiak
2015 J jnl
Robustly Solvable Constraint Satisfaction Problems.
CoRR
Libor Barto, Marcin Kozik
2014 J jnl
Constraint Satisfaction Problems Solvable by Local Consistency Methods.
J. ACM
Libor Barto, Marcin Kozik
2012 J jnl
Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
Log. Methods Comput. Sci.
Libor Barto, Marcin Kozik
2012 A* conf
Near Unanimity Constraints Have Bounded Pathwidth Duality.
LICS
Libor Barto, Marcin Kozik, Ross Willard
2012 A* conf
Robust satisfiability of constraint satisfaction problems.
STOC
Libor Barto, Marcin Kozik
2011 J jnl
Robust Satisfiability of Constraint Satisfaction Problems.
Electron. Colloquium Comput. Complex.
Libor Barto, Marcin Kozik
2010 A* conf
New Conditions for Taylor Varieties and CSP.
LICS
Libor Barto, Marcin Kozik
2009 J jnl
A 2EXPTIME Complete Varietal Membership Problem.
SIAM J. Comput.
Marcin Kozik
2009 J jnl
Congruence Distributivity Implies Bounded Width.
SIAM J. Comput.
Libor Barto, Marcin Kozik
2009 A* conf
Constraint Satisfaction Problems of Bounded Width.
FOCS
Libor Barto, Marcin Kozik
2009 J jnl
The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell).
SIAM J. Comput.
Libor Barto, Marcin Kozik, Todd Niven
2008 J jnl
A finite set of functions with an EXPTIME-complete composition problem.
Theor. Comput. Sci.
Marcin Kozik
2008 A* conf
Graphs, polymorphisms and the complexity of homomorphism problems.
STOC
Libor Barto, Marcin Kozik, Todd Niven
2007 J jnl
Computationally and Algebraically Complex Finite Algebra Membership Problems.
Int. J. Algebra Comput.
Marcin Kozik