Theoretical Computer Science flagPL flagEN
Faculty of Mathematics and Computer Science
Jagiellonian University
    informatyka analityczna  
UJ coat of arms
Algorithmics Research Group abacus

Marcin Kozik


phone: (+48-12) 664 75 62
fax: (+48-12) 664 66 72
email: email
office: ul. Łojasiewicza 6, 30-348 Kraków
room: 3055
office hours: Tuesday 12:00 - 14:00
Friday 10:00 - 12:00
for students

research interests
universal algebra
computational complexity theory
Constraint Satisfaction Problem

selected publications
  • Libor Barto, Marcin Kozik
         Absorbing subuniverses and Mal'cev conditions
         [in preparation]
  • Libor Barto, Marcin Kozik
         Constraint satisfaction problems solvable by local consistency methods
         [to appear, Journal of the ACM]
  • Libor Barto, Marcin Kozik
         Absorbing subalgebra, cyclic terms and the Constraint Satisfaction Problem
         [Logical Methods in Computer Science 8(2012), issue 1, paper 7]
              conference version:
              New conditions for Taylor varieties and CSP
              [Proceedings of 25th IEEE Symposium on Logic in Computer Science, LICS'10, 100-109]
  • Libor Barto, Marcin Kozik, Ross Willard
         Near unanimity constraints have bounded pathwidth duality
         [Proceedings of the 27th IEEE/ACM Symposium on Logic in Computer Science LICS'12, 125-134] [manuscript]
  • Libor Barto, Marcin Kozik
         Robust Satisfiability of Constraint Satisfaction Problems
         [Proceedings of the 44th ACM Symposium on Theory of Computing, STOC'12, 931-940] [ECCC report]
  • Libor Barto, Marcin Kozik
         Cyclic terms for SD(V) varieties revisited
         [Algebra Universalis 64(2010) 137-142]
  • Libor Barto, Marcin Kozik, Miklos Maroti, Ralph McKenzie, Todd Niven
         Congruence modularity implies cyclic terms for finite algebras
         [Algebra Universalis 61(2009) 365-380] [manuscript]
  • Libor Barto, Marcin Kozik
         Constraint Satisfaction Problems of Bounded Width
         [Proceedings of the 50th Symposium on Foundations of Computer Science, FOCS'09, 595-603]
  • Libor Barto, Marcin Kozik, Miklos Maroti, Todd Niven
         CSP dichotomy for special triads
         [Proceedings of the Amer. Math. Soc. 137(2009) 2921-2934]
  • Libor Barto, Marcin Kozik
         Congruence distributivity implies bounded width
         [SIAM Journal on Computing, Volume 39, Issue 4, pp. 1531-1542 (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 Journal on Computing 38(2009), Issue 5, pp. 1782-1802] [manuscript]
              conference version:
              Graphs, polymorphisms and the complexity of homomorphism problems
              [Proceedings of the 40th ACM Symposium on Theory of Computing, STOC'08, 789-796]
  • Marcin Kozik, Gabor Kun
         The subdirectly irreducible algebras in the variety generated by graph algebras
         [Algebra Universalis 58(2008) 229-242]
  • Marcin Kozik
         A finite set of functions with an EXPTIME-complete composition problem
         [Theoretical Computer Science 407(2008) 330-341] [manusript]
  • Marcin Kozik
         A 2EXPTIME Complete Varietal Membership Problem
         [SIAM Journal on Computing, Volume 38, Issue 6, pp. 2443-2467 (2009)] [manuscript]
  • Marcin Kozik
         Computationally and algebraically complex finite algebra membership problems
         [International Journal of Algebra and Computation 17(2007) 1635-1666] [manuscript]
  • Iwona Cieślik, Marcin Kozik, Piotr Micek
         On-line coloring of Is-free graphs and co-planar graphs
         [Discrete Mathematics and Theoretical Computer Science Proceedings AF (2006), 61-68]
  • Marcin Kozik
         On some complexity problems in finite algebras
         [dissertation, Vanderbilt University]
  • Marcin Kozik
         Measurements of object complexity
         [masters thesis, Jagiellonian University]

  • some recent collaborators 
    Libor BartoCharles University, Prague
    Todd Niven

    2008 - 2009 Algebraic aproach to Constraint Satisfaction Problem
      Ministry of Science and Higher Education
      Polish-Czech Project (with Charles University Prague)
    2008 - 2010
      Foundation for Polish Science
      HOMING 2008
    2009 - 2011 Algebraic approach to Constraint Satisfaction Problem
      Ministry of Science and Higher Education
      N 206 3570 36
    2011 - 2014 DATALOG in Constraints Satisfaction Problem
      Polish National Science Center

    short cv
    2000Master of Science in Computer ScienceJagiellonian UniversityKrakow, Poland
    2002Master of Science in MathematicsVanderbilt UniversityNashville, TN
    2004Philosophy Doctor in MathematicsVanderbilt UniversityNashville, TN
    2004Jonsson prize for the best graduate student researchVanderbilt UniversityNashville, TN
    2004AssistantJagiellonian UniversityKrakow, Poland
    2006PostdocCharles University and
    Eduard Čech Center
    Prague, Czech Republic
    2007Associate ProfessorJagiellonian UniversityKrakow, Poland
    2007PostdocCharles University and
    Eduard Čech Center
    Prague, Czech Republic
    2010Visiting ScholarVanderbilt UniversityNashville, TN
    2011Visiting ProfessorVanderbilt UniversityNashville, TN
      webmaster: email = a@b, a=www-tcs,