| 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 |
Full characterization of cyclic terms (for finite algebras) [in preparation] |
SD-meet and bounded width [in preparation] |
Cyclic terms for SD(V) varieties revisited [to appear, Algebra Universalis] |
Congruence modularity implies cyclic terms for finite algebras [Algebra Universalis 61(2009) 365-380] [manuscript] |
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, Volume 38, Issue 5, pp. 1782-1802 (2009)] [manuscript] |
CSP dichotomy for special triads [Proceedings of the Amer. Math. Soc. 137(2009) 2921-2934] |
Constraint Satisfaction Problems of Bounded Width [Proceedings of the 50th Symposium on Foundations of Computer Science, FOCS'09, 595-603] |
Congruence distributivity implies bounded width [SIAM Journal on Computing, Volume 39, Issue 4, pp. 1531-1542 (2009)] |
Varietal membership problem is 2EXPTIME complete [SIAM Journal on Computing, Volume 38, Issue 6, pp. 2443-2467 (2009)] [manuscript] |
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] |
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 | |||
| 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 |
| 2008 | Homing grant | Foundation for Polish Science | Poland |
