Foundations of Computer Science

Theoretical Computer Science
Faculty of Mathematics and Computer Science
Jagiellonian University

Foundations of Computer Science

Jakub Kozik

PhD

phone:	(+48-12) 664 75 57
fax:	(+48-12) 664 66 72
email:
office:	ul. Łojasiewicza 6, 30-348 Kraków
room:	3060
office hours:	Wednesday 15:00 - 16:00
	Thursday 11:00 - 12:00


phd thesis:	[pdf]

research interests

logic

analytic combinatorics

probabilistic method

graph choosability

selected publications

Jakub Kozik and Piotr Micek,
Nonrepetitive colorings of trees,
[submitted]

Jakub Kozik, Piotr Micek and Xuding Zhu,
Towards on-line Ohba’s conjecture, [pdf]
[submitted]

Vida Dujmović, Gwenaël Joret, Jakub Kozik, David R. Wood,
Nonrepetitive Colouring via Entropy Compression
[submitted]

René David, Christophe Raffalli, Guillaume Theyssier, Katarzyna Grygiel, Jakub Kozik, Marek Zaionc,
Some properties of random lambda terms,
[submitted]

Jarosław Grytczuk, Jakub Kozik and Piotr Micek,
A new approach to nonrepetitive sequences, [pdf]
[accepted in Random Structures and Algorithms]

Antoine Genitrini, Jakub Kozik,
In the full propositional logic, 5/8 of classical tautologies are intuitionistically valid [link]
[Annals of Pure and Applied Logic, Volume 163, Issue 7, July 2012, pp. 875–887]

Jarosław Grytczuk, Jakub Kozik, Marcin Witkowski,
Nonrepetitive sequences on arithmetic progressions [pdf]
[Electronic Journal of Combinatorics 18, 2011]

Jakub Kozik,
Dynamic Threshold Strategy for Universal Best Choice Problem,
[DMTCS Proceedings, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms, (2010), 439–452. ]

Antoine Genitrini, Jakub Kozik,
Quantitative comparison of Intuitionistic and Classical logics - full propositional system,
[LFCS09, Lecture Notes in Computer Science 5407 (2009) pp. 280-294]

Antoine Genitrini, Jakub Kozik, Grzegorz Matecki,
On the density and the structure of the Peirce-like formulae,
[DMTCS proc. from Fifth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, 2008, pp. 461-474]

Jakub Kozik,
Subcritical pattern languages for and/or trees
[DMTCS proc. from Fifth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, 2008, pp. 437-448]

Antoine Genitrini, Jakub Kozik, Marek Zaionc
Intuitionistic vs. Classical Tautologies, Quantitative Comparison,
[TYPES 2007, Lecture Notes in Computer Science 4941 (2008) pp. 100-109.]

Jakub Kozik,
Undecidable problems concerning densities of languages,
[Computational Logic and Applications, CLA 05, David, Rene and Gardy, Daniele and Lescanne, Pierre and Zaionc, Marek (eds.), Discrete Mathematics and Theoretical Computer Science (Proceedings AF), pp. 69-76]

Jakub Kozik,
Conditional Densities of Regular Languages,
[Electronic Notes in Theoretical Computer Science , 140(2005), 67-79]

some recent collaborators
Antoine Genitrini	University Pierre and Marie Curie
Jarosław Grytczuk	Jagiellonian University
Piotr Micek	Jagiellonian University
Xuding Zhu	Zhejiang Normal University

grants
2004 - 2006	Types for programs and proofs
	EU, szósty program ramowy
	Project of 35 European Universities,
	contract number 510996.
2006 - 2008	Quantitative research in logic and functional languages
	POLONIUM grant
	Cooperation between TCS and L Ecole Normale Superieure de Lyon and Universite de Versailles Saint-Quentin.
	7087/R07/R08
2008 - 2008	Research on large scale mailing system
	Ministry of Science and Higher Education, Interia.pl S.A.
2009 - 2012	Quantitative study in logics and computation theory
	Ministry of Science and Higher Education
	N206 3761 37
2010 - 2012	Movement tracking in monitored zones
	Ministry of Science and Higher Education
	R00 0081 11
2011 - 2012	Quantitative logic
	Ministry of Science and Higher Education,
	8434/2011
2011 - 2014	Algorithmic Local Lovász Lemma as double counting
	Polish National Science Center
	2011/01/D/ST1/04412

short cv
2002	M.S. (computer science)	Jagiellonian University	Krakow, Poland
2006	PhD (computer science)	Jagiellonian University	Krakow, Poland
2007	Three months visit at Computer Science Department	Universite de Versailles Saint-Quentin-en-Yvelines	France
2011	Two months visit at Center for Discrete Mathematics	Zhejiang Normal University	Jinhua, China

webmaster: email = a@b, a=www-tcs, b=tcs.uj.edu.pl