Marcin Kozik

Publication Activity (10 Years)

Years Active: 2007-2024
Publications (10 Years): 24

Top Topics

Disjunctive Temporal

Decomposition Methods

Algebraic Properties

Constraint Satisfaction

Top Venues

SIAM J. Comput.

Publications

Demian Banakh, Marcin Kozik
Injective hardness condition for PCSPs. LICS (2024)
Demian Banakh, Marcin Kozik
Injective hardness condition for PCSPs. CoRR (2024)
Lorenzo Ciardo, Marcin Kozik, Andrei A. Krokhin, Tamio-Vesa Nakajima, Stanislav Zivný
1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise. LICS (2024)
Lorenzo Ciardo, Marcin Kozik, Andrei A. Krokhin, Tamio-Vesa Nakajima, Stanislav Zivný
On the complexity of the approximate hypergraph homomorphism problem. CoRR (2023)
Libor Barto, Bertalan Bodor, Marcin Kozik, Antoine Mottet, Michael Pinsker
Symmetries of structures that fail to interpret something finite. CoRR (2023)
Libor Barto, Bertalan Bodor, Marcin Kozik, Antoine Mottet, Michael Pinsker
Symmetries of Graphs and Structures that Fail to Interpret a Finite Thing. LICS (2023)
Libor Barto, Marcin Kozik
Combinatorial Gap Theorem and Reductions between Promise CSPs. SODA (2022)
Libor Barto, Marcin Kozik
Combinatorial Gap Theorem and Reductions between Promise CSPs. CoRR (2021)
Marcin Kozik
Solving CSPs Using Weak Local Consistency. SIAM J. Comput. 50 (4) (2021)
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. LICS (2021)
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. CoRR (2021)
Libor Barto, Marcin Kozik, Johnson Tan, Matt Valeriote
Sensitive Instances of the Constraint Satisfaction Problem. ICALP (2020)
Libor Barto, Marcin Kozik, Johnson Tan, Matt Valeriote
Sensitive instances of the Constraint Satisfaction Problem. CoRR (2020)
Miron Ficak, Marcin Kozik, Miroslav Olsák, Szymon Stankiewicz
Dichotomy for Symmetric Boolean PCSPs. ICALP (2019)
Miron Ficak, Marcin Kozik, Miroslav Olsák, Szymon Stankiewicz
Dichotomy for symmetric Boolean PCSPs. CoRR (2019)
Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal
Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs. SIAM J. Comput. 48 (6) (2019)
Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal
Robust algorithms with polynomial loss for near-unanimity CSPs. SODA (2017)
Libor Barto, Marcin Kozik
Robustly Solvable Constraint Satisfaction Problems. SIAM J. Comput. 45 (4) (2016)
Marcin Kozik
Weaker consistency notions for all the CSPs of bounded width. CoRR (2016)
Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal
Robust algorithms with polynomial loss for near-unanimity CSPs. CoRR (2016)
Marcin Kozik
Weak consistency notions for all the CSPs of bounded width. LICS (2016)
Andrei Bulatov, Marcin Kozik, Peter Mayr, Markus Steindl
The subpower membership problem for semigroups. Int. J. Algebra Comput. 26 (7) (2016)
Marcin Kozik, Joanna Ochremiak
Algebraic Properties of Valued Constraint Satisfaction Problem. ICALP (1) (2015)
Libor Barto, Marcin Kozik
Robustly Solvable Constraint Satisfaction Problems. CoRR (2015)
Libor Barto, Marcin Kozik
Constraint Satisfaction Problems Solvable by Local Consistency Methods. J. ACM 61 (1) (2014)
Libor Barto, Marcin Kozik
Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem Log. Methods Comput. Sci. 8 (1) (2012)
Libor Barto, Marcin Kozik
Robust satisfiability of constraint satisfaction problems. STOC (2012)
Libor Barto, Marcin Kozik, Ross Willard
Near Unanimity Constraints Have Bounded Pathwidth Duality. LICS (2012)
Libor Barto, Marcin Kozik
Robust Satisfiability of Constraint Satisfaction Problems. Electron. Colloquium Comput. Complex. 18 (2011)
Libor Barto, Marcin Kozik
New Conditions for Taylor Varieties and CSP. LICS (2010)
Marcin Kozik
A 2EXPTIME Complete Varietal Membership Problem. SIAM J. Comput. 38 (6) (2009)
Libor Barto, Marcin Kozik
Congruence Distributivity Implies Bounded Width. SIAM J. Comput. 39 (4) (2009)
Libor Barto, Marcin Kozik, Todd Niven
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. 38 (5) (2009)
Libor Barto, Marcin Kozik
Constraint Satisfaction Problems of Bounded Width. FOCS (2009)
Marcin Kozik
A finite set of functions with an EXPTIME-complete composition problem. Theor. Comput. Sci. 407 (1-3) (2008)
Libor Barto, Marcin Kozik, Todd Niven
Graphs, polymorphisms and the complexity of homomorphism problems. STOC (2008)
Marcin Kozik
Computationally and Algebraically Complex Finite Algebra Membership Problems. Int. J. Algebra Comput. 17 (8) (2007)