2014
2015
2016
2017
2018
2019
2020
2022
2023
2024

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 typically takes place on Thursdays at 4:15pm in lecture rooms of the Czech Technical University in Prague or the Charles University.

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 are in English.

The seminar is organized by the organizational committee consisting of Roman Barták (Charles University, Faculty of Mathematics and Physics), Jaroslav Hlinka (Czech Academy of Sciences, Computer Science Institute), Michal Chytil, Pavel Kordík (CTU in Prague, Faculty of Information Technologies), Michal Koucký (Charles University, Faculty of Mathematics and Physics), Jan Kybic (CTU in Prague, Faculty of Electrical Engineering), Michal Pěchouček (CTU in Prague, 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 (CTU in Prague, Faculty of Electrical Engineering), and Filip Železný (CTU in Prague, 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

Prague computer science seminar is suspended until further notice to prevent spread of the new coronavirus.