2014
2015
2016
2017

The tenth meeting of the Prague computer science seminar

Jaroslav Nešetřil

Sparsity and fast algorithms for combinatorial problems

Combinatorial problems reflect some of the core situations of both theoretical and engineering computer science.

Followed by a discussion

January 22, 2015

4:00pm

Auditorium E-107, FEL CTU
Karlovo nám. 13, Praha 2
Show on the map

Lecture annotation

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.

Lecturer

Prof. RNDr. Jaroslav Nešetřil, DrSc., Dr.h.c.mult.

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.

ABOUT THE PRAGUE COMPUTER SCIENCE SEMINAR

The seminar takes place on the 4th Thursday of each month at 4:00pm (except June, July, August and December) alternately in the buildings of Faculty of Electrical Engineering, Czech Technical University, Karlovo nám. 13, Praha 2 and Faculty of Mathematics and Physics, Charles University, Malostranské nám. 25, Praha 1.

Its program consists of a one-hour lecture followed by a discussion. The lecture is based on an (internationally) exceptional or remarkable achievement of the lecturer, presented in a way which is comprehensible and interesting to a broad computer science community. The lectures is in English.

The seminar is organized by the organizational committee consisting of Roman Barták (Charles University, Faculty of Mathematics and Physics), Michal Chytil (Czech Academy of Sciences, Computer Science Institute), Pavel Kordík (Czech Tech. Univ., Faculty of Information Technologies), Jan Kybic (Czech Tech. Univ., Faculty of Electrical Engineering), Michal Pěchouček (Czech Tech. Univ., Faculty of Electrical Engineering), Jiří Sgall (Charles University, Faculty of Mathematics and Physics), Vojtěch Svátek (University of Economics, Faculty of Informatics and Statistics), Michal Šorel (Czech Academy of Sciences, Institute of Information Theory and Automation), Tomáš Werner (Czech Tech. Univ., Faculty of Electrical Engineering), and Filip Železný (Czech Tech. Univ., Faculty of Electrical Engineering)

The idea to organize this seminar emerged in discussions of the representatives of several research institutes on how to avoid the undesired fragmentation of the Czech computer science community.

Supporters

Contact