The Prague Informatic Seminar coorganized by Department of Computer Science, presents
Sparsity and fast algorithms for combinatorial problems by Jaroslav Nešetřil
Thursday, January 22 at 4 p.m. in room KNE:107.
Combinatorial problems reflect some of the core situations of both theoretical and engineering computer science. To find broad classes of problems which can be effectively solved is of pivotal importance and this in turn leads to some popular dichotomies. We survey the recent development particularly from the point of view of the sparse vs dense dichotomy.
More about lecturer:
Prof. RNDr. Jaroslav Nešetřil, DrSc., Dr.h.c.mult., is one of the world leaders in discrete mathematics. He specializes in combinatorics, graph theory and theory of combinatorial structures including their representations and homomorphisms; he is also active in theoretical computer science (complexity and theory of algorithms). He authored 9 monographs and more than 300 journal research papers. He is a professor at Faculty of Mathematics and Physics of Charles University in Prague. Prof. Nešetřil has founded and led for 15 years the center Institute for Theoretical Computer Science, which significantly contributes to development and organization of various activities in theoretical computer science. He has also founded and is now active in the Computer Science Institute of Charles University. He lectured at numerous academic institutions and conferences, including invited talks at the European Congress of Mathematics (2006) and at the International Congress of Mathematicians (2010). He received the State prize (1985 jointly with Vojtěch Rödl) and the Medal of Merit of the Czech Republic (2010). He is a corresponding member of the German Academy of Sciences, Hungarian Academy of Sciences and Academia Europeana; since 2008 he is a member of Advisory Board of the Academia Sinica. He has been declared Doctor Honoris Causa of the University of Alaska (Fairbanks) in 2002 and of Université de Bordeaux in 2009). His Erdös number is 1.