Theoretical Computer Science flagPL flagEN
Faculty of Mathematics and Computer Science
Jagiellonian University
 
    informatyka analityczna  
UJ coat of arms
Foundations of Computer Science
 
 

Jakub Kozik

PhD

phone: (+48-12) 664 75 57
fax: (+48-12) 664 66 72
email: email
office: ul. Łojasiewicza 6, 30-348 Kraków
room: 3060
office hours: Tuesday 14:30 - 16:00
 
 
phd thesis:[pdf]
photo

research interests
analytic combinatorics
probabilistic method
graph choosability

selected publications
  • Lech Duraj, Grzegorz Gutowski, Jakub Kozik,
    Chip games and paintability, [arXiv]
    [preprint]
  • Jakub Kozik, Grzegorz Matecki,
    Lazy approach to on-line bipartite matching, [arXiv]
    [submitted]
  • Jakub Kozik, Dmitry Shabanov
    Improved algorithms for colorings of simple hypergraphs and applications, [arXiv]
    [submitted]
  • Jakub Kozik,
    Multipass greedy coloring of simple uniform hypergraphs, [arXiv]
    [submitted]
  • Danila D. Cherkashin, Jakub Kozik,
    A note on random greedy coloring of uniform hypergraphs, [arXiv]
    [to appear in Random Structures and Algorithms]
  • Vida Dujmović, Gwenaël Joret, Jakub Kozik, David R. Wood,
    Nonrepetitive Colouring via Entropy Compression [arXiv]
    [to appear in Combinatorica]
  • Arkadiusz Pawlik, Jakub Kozik, Tomasz Krawczyk, Michał Lasoń, Piotr Micek, William T. Trotter and Bartosz Walczak,
    Triangle-free intersection graphs of line segments with large chromatic number, [arXiv]
    [Journal of Combinatorial Theory, Series B, Volume 105, March 2014, pp. 6–10]
  • Jakub Kozik, Piotr Micek and Xuding Zhu,
    Towards an on-line version of Ohba’s conjecture, [arXiv]
    [European Journal of Combinatorics, Volume 36, February 2014, pp. 110–121]
  • Grzegorz Gutowski, Jakub Kozik, Piotr Micek and Xuding Zhu,
    Lower bounds for on-line graph colorings, [arXiv]
    [Algorithms and Computation - 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings, 507--515 (2014)]
  • Jarosław Grytczuk, Jakub Kozik and Piotr Micek,
    New approach to nonrepetitive sequences,[arXiv]
    [Random Structures and Algorithms 42, issue 2 (2013), pp. 214–225]
  • Arkadiusz Pawlik, Jakub Kozik, Tomasz Krawczyk, Michał Lasoń, Piotr Micek, William T. Trotter and Bartosz Walczak,
    Triangle-free geometric intersection graphs with large chromatic number, [arXiv]
    [Discrete & Computational Geometry, October 2013, Volume 50, Issue 3, pp 714-726]
  • René David, Christophe Raffalli, Guillaume Theyssier, Katarzyna Grygiel, Jakub Kozik, Marek Zaionc,
    Asymptotically almost all lambda-terms are strongly normalizing, [arXiv]
    [Logical Methods in Computer Science Vol. 9(1:02)2013, pp. 1–30]
  • Jakub Kozik and Piotr Micek,
    Nonrepetitive choice number of trees, [arXiv]
    [SIAM J. Discrete Math. 27-1 (2013), pp. 436-446]
  • 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, [link]
    [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, [link]
    [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 [link]
    [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 GenitriniUniversity Pierre and Marie Curie
    Jarosław GrytczukJagiellonian University
    Piotr MicekJagiellonian University
    Xuding ZhuZhejiang 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
    2012 - 2015 On-line choosability
      Polish National Science Center
      UMO-2011/03/D/ST6/01370

    short cv
    2002M.S. (computer science)Jagiellonian UniversityKrakow, Poland
    2006PhD (computer science)Jagiellonian UniversityKrakow, Poland
    2007Three months visit at Computer Science DepartmentUniversite de Versailles Saint-Quentin-en-YvelinesFrance
    2011Two months visit at Center for Discrete MathematicsZhejiang Normal UniversityJinhua, China
     
     
      webmaster: email = a@b, a=www-tcs, b=tcs.uj.edu.pl