| Theoretical Computer Science |
|
| Faculty of Mathematics and Computer Science | |
| Jagiellonian University |
| Algorithmics Research Group |
|
Marcin KozikPhD
| |||||||||||||||||||
| research interests |
| universal algebra |
| computational complexity theory |
| Constraint Satisfaction Problem |
| selected publications |
Absorbing subuniverses and Mal'cev conditions [in preparation] |
Constraint satisfaction problems solvable by local consistency methods [to appear, Journal of the ACM] |
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] |
Near unanimity constraints have bounded pathwidth duality [Proceedings of the 27th IEEE/ACM Symposium on Logic in Computer Science LICS'12, 125-134] [manuscript] |
Robust Satisfiability of Constraint Satisfaction Problems [Proceedings of the 44th ACM Symposium on Theory of Computing, STOC'12, 931-940] [ECCC report] |
Cyclic terms for SD(V) varieties revisited [Algebra Universalis 64(2010) 137-142] |
Congruence modularity implies cyclic terms for finite algebras [Algebra Universalis 61(2009) 365-380] [manuscript] |
Constraint Satisfaction Problems of Bounded Width [Proceedings of the 50th Symposium on Foundations of Computer Science, FOCS'09, 595-603] |
CSP dichotomy for special triads [Proceedings of the Amer. Math. Soc. 137(2009) 2921-2934] |
Congruence distributivity implies bounded width [SIAM Journal on Computing, Volume 39, Issue 4, pp. 1531-1542 (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 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] |
The subdirectly irreducible algebras in the variety generated by graph algebras [Algebra Universalis 58(2008) 229-242] |
A finite set of functions with an EXPTIME-complete composition problem [Theoretical Computer Science 407(2008) 330-341] [manusript] |
A 2EXPTIME Complete Varietal Membership Problem [SIAM Journal on Computing, Volume 38, Issue 6, pp. 2443-2467 (2009)] [manuscript] |
Computationally and algebraically complex finite algebra membership problems [International Journal of Algebra and Computation 17(2007) 1635-1666] [manuscript] |
On-line coloring of Is-free graphs and co-planar graphs [Discrete Mathematics and Theoretical Computer Science Proceedings AF (2006), 61-68] |
On some complexity problems in finite algebras [dissertation, Vanderbilt University] |
Measurements of object complexity [masters thesis, Jagiellonian University] |
| some recent collaborators | |
| Libor Barto | Charles University, Prague |
| Todd Niven |
| grants | |||
| 2008 - 2009 | Algebraic aproach to Constraint Satisfaction Problem | ||
| Ministry of Science and Higher Education | |||
| Polish-Czech Project (with Charles University Prague) | |||
| 7426/2008 | |||
| 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 | |||
| 2011/01/B/ST6/01006 | |||
| short cv | |||
| 2000 | Master of Science in Computer Science | Jagiellonian University | Krakow, Poland |
| 2002 | Master of Science in Mathematics | Vanderbilt University | Nashville, TN |
| 2004 | Philosophy Doctor in Mathematics | Vanderbilt University | Nashville, TN |
| 2004 | Jonsson prize for the best graduate student research | Vanderbilt University | Nashville, TN |
| 2004 | Assistant | Jagiellonian University | Krakow, Poland |
| 2006 | Postdoc | Charles University and Eduard Čech Center | Prague, Czech Republic |
| 2007 | Associate Professor | Jagiellonian University | Krakow, Poland |
| 2007 | Postdoc | Charles University and Eduard Čech Center | Prague, Czech Republic |
| 2010 | Visiting Scholar | Vanderbilt University | Nashville, TN |
| 2011 | Visiting Professor | Vanderbilt University | Nashville, TN |
