|
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 |
CSP dichotomy for special triads [in preparation] |
Varietal membership problem is 2EXPTIME complete [submitted] [manuscript] |
The CSP dichotomy holds for digraphs with no sources and no sinks (a positive answer to a conjecture of Bang-Jensen and Hell) [to appear, SIAM Journal on Computing] [manuscript] |
Congruence modularity implies cyclic terms (for finite algebras) [to appear, Algebra Universalis] [manuscript] |
A finite set of functions with an EXPTIME-complete composition problem [to appear, Theoretical Computer Science] [manusript] |
The subdirectly irreducible algebras in the variety generated by graph algebras [Algebra Universalis 58(2008) 229-242] |
Graphs, polymorphisms and the complexity of homomorphism problems [Proceedings of the 40th ACM Symposium on Theory of Computing, STOC'08, 789-796] |
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 |
| 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 |