Marcin Kozik

According to our database, Marcin Kozik authored at least 31 papers between 2007 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

Unifying the Three Algebraic Approaches to the CSP via Minimal Taylor Algebras.

Libor Barto, Zarathustra Brady, Andrei Bulatov, Marcin Kozik, Dmitriy Zhuk

TheoretiCS, 2024

Model-checking positive equality free logic on a fixed structure (direttissima).

Manuel Bodirsky, Marcin Kozik, Florent R. Madelaine, Barnaby Martin, Michal Wrona

CoRR, 2024

1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise.

Lorenzo Ciardo, Marcin Kozik, Andrei A. Krokhin, Tamio-Vesa Nakajima, Stanislav Zivný

Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, 2024

Injective hardness condition for PCSPs.

Demian Banakh, Marcin Kozik

Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, 2024

2023

Symmetries of structures that fail to interpret something finite.

Libor Barto, Bertalan Bodor, Marcin Kozik, Antoine Mottet, Michael Pinsker

CoRR, 2023

On the complexity of the approximate hypergraph homomorphism problem.

Lorenzo Ciardo, Marcin Kozik, Andrei A. Krokhin, Tamio-Vesa Nakajima, Stanislav Zivný

CoRR, 2023

Symmetries of Graphs and Structures that Fail to Interpret a Finite Thing.

Libor Barto, Bertalan Bodor, Marcin Kozik, Antoine Mottet, Michael Pinsker

Proceedings of the 38th Annual ACM/IEEE Symposium on Logic in Computer Science, 2023

2022

Combinatorial Gap Theorem and Reductions between Promise CSPs.

Libor Barto, Marcin Kozik

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

2021

Solving CSPs Using Weak Local Consistency.

Marcin Kozik

SIAM J. Comput., 2021

Minimal Taylor Algebras as a Common Framework for the Three Algebraic Approaches to the CSP.

Libor Barto, Zarathustra Brady, Andrei Bulatov, Marcin Kozik, Dmitriy Zhuk

Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, 2021

2020

Sensitive Instances of the Constraint Satisfaction Problem.

Libor Barto, Marcin Kozik, Johnson Tan, Matt Valeriote

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

2019

Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs.

Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal

SIAM J. Comput., 2019

Dichotomy for Symmetric Boolean PCSPs.

Miron Ficak, Marcin Kozik, Miroslav Olsák, Szymon Stankiewicz

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2017

Absorption in Universal Algebra and CSP.

Libor Barto, Marcin Kozik

Proceedings of the Constraint Satisfaction Problem: Complexity and Approximability, 2017

2016

Robustly Solvable Constraint Satisfaction Problems.

Libor Barto, Marcin Kozik

SIAM J. Comput., 2016

The subpower membership problem for semigroups.

Andrei Bulatov, Marcin Kozik, Peter Mayr, Markus Steindl

Int. J. Algebra Comput., 2016

Weaker consistency notions for all the CSPs of bounded width.

Marcin Kozik

CoRR, 2016

Weak consistency notions for all the CSPs of bounded width.

Marcin Kozik

Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, 2016

2015

Algebraic Properties of Valued Constraint Satisfaction Problem.

Marcin Kozik, Joanna Ochremiak

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014

Constraint Satisfaction Problems Solvable by Local Consistency Methods.

Libor Barto, Marcin Kozik

J. ACM, 2014

2012

Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem

Libor Barto, Marcin Kozik

Log. Methods Comput. Sci., 2012

Near Unanimity Constraints Have Bounded Pathwidth Duality.

Libor Barto, Marcin Kozik, Ross Willard

Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science, 2012

2011

Robust Satisfiability of Constraint Satisfaction Problems.

Libor Barto, Marcin Kozik

Electron. Colloquium Comput. Complex., 2011

2010

New Conditions for Taylor Varieties and CSP.

Libor Barto, Marcin Kozik

Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science, 2010

2009

A 2EXPTIME Complete Varietal Membership Problem.

Marcin Kozik

SIAM J. Comput., 2009

The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell).

Libor Barto, Marcin Kozik, Todd Niven

SIAM J. Comput., 2009

Congruence Distributivity Implies Bounded Width.

Libor Barto, Marcin Kozik

SIAM J. Comput., 2009

Constraint Satisfaction Problems of Bounded Width.

Libor Barto, Marcin Kozik

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

2008

A finite set of functions with an EXPTIME-complete composition problem.

Marcin Kozik

Theor. Comput. Sci., 2008

Graphs, polymorphisms and the complexity of homomorphism problems.

Libor Barto, Marcin Kozik, Todd Niven

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

2007

Computationally and Algebraically Complex Finite Algebra Membership Problems.

Marcin Kozik

Int. J. Algebra Comput., 2007