Marcin Kozik

Affiliations:
  • Jagiellonian University, Kraków, Poland


According to our database1, Marcin Kozik authored at least 27 papers between 2007 and 2023.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2023
Symmetries of structures that fail to interpret something finite.
CoRR, 2023

On the complexity of the approximate hypergraph homomorphism problem.
CoRR, 2023

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

2022
Combinatorial Gap Theorem and Reductions between Promise CSPs.
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

2021
Solving CSPs Using Weak Local Consistency.
SIAM J. Comput., 2021

Minimal Taylor Algebras as a Common Framework for the Three Algebraic Approaches to the CSP.
Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, 2021

2020
Sensitive Instances of the Constraint Satisfaction Problem.
Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

2019
Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs.
SIAM J. Comput., 2019

Dichotomy for Symmetric Boolean PCSPs.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2017
Absorption in Universal Algebra and CSP.
Proceedings of the Constraint Satisfaction Problem: Complexity and Approximability, 2017

2016
Robustly Solvable Constraint Satisfaction Problems.
SIAM J. Comput., 2016

The subpower membership problem for semigroups.
Int. J. Algebra Comput., 2016

Weaker consistency notions for all the CSPs of bounded width.
CoRR, 2016

Weak consistency notions for all the CSPs of bounded width.
Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, 2016

2015
Algebraic Properties of Valued Constraint Satisfaction Problem.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014
Constraint Satisfaction Problems Solvable by Local Consistency Methods.
J. ACM, 2014

2012
Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
Log. Methods Comput. Sci., 2012

Near Unanimity Constraints Have Bounded Pathwidth Duality.
Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science, 2012

2011
Robust Satisfiability of Constraint Satisfaction Problems.
Electron. Colloquium Comput. Complex., 2011

2010
New Conditions for Taylor Varieties and CSP.
Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science, 2010

2009
A 2EXPTIME Complete Varietal Membership Problem.
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).
SIAM J. Comput., 2009

Congruence Distributivity Implies Bounded Width.
SIAM J. Comput., 2009

Constraint Satisfaction Problems of Bounded Width.
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.
Theor. Comput. Sci., 2008

Graphs, polymorphisms and the complexity of homomorphism problems.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

2007
Computationally and Algebraically Complex Finite Algebra Membership Problems.
Int. J. Algebra Comput., 2007


  Loading...