2014
2015
2016
2017

The seventh meeting of the Prague computer science seminar

Daniel Kráľ

Mathematics and fast algorithms

Mathematical methods, in particular those coming from combinatorics and logic, find applications in various areas of computer science. An area where such methods are often used is algorithm...

October 23, 2014

4:00pm

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

Lecture annotation

Mathematical methods, in particular those coming from combinatorics and logic, find applications in various areas of computer science. An area where such methods are often used is algorithm and data structure design. However, many important algorithmic problems are hard in the sense of computational complexity and it is unlikely that they can be efficiently solved in full generality. One of the approaches to cope with this is based on restricting the hardness by an appropriate parameterization, e.g., by restricting the structure of input data or the logic complexity of considered problems.

The lecture will start with a demonstration how mathematical methods can be used to design an algorithm for a particular problem. The case study presented will be used to introduce concepts from the parameterized complexity and some of the basic results in this area. At the end of the lecture, we will give several general results that were proved using methods from combinatorics and logic. These results known as algorithms metatheorems guarantee the existence of efficient algorithms for a wide range of algorithmic problems.

Lecturer

Prof. Daniel Kráľ

Prof. Daniel Kráľ is an internationally recognized researcher in combinatorics and graph theory. In addition to the algorithmic questions, that are the topic of this presentation, he studies structural graph theory, in particular graph colorings, extremal combinatorics, and combinatorial limits. He has published more than 100 journal papers, including ones in top journals Advances in Mathematics, Geometric and Functional Analysis, and Journal of the ACM. He also has numerous publications in the top selective theoretical computer science conferences including FOCS, SODA, ICALP. He was the first member of Czech computer science community who received ERC grant (starting grant). Other awards include the European Prize in Combinatorics and Bolzano Award, he was the absolute winner of the International Olympiad in Informatics (one of only two Czech absolute winners in the history). Except for Charles University in Prague he held positions at Georgia Inst. of Technology and TU Berlin; currently he is a professor at Univ. of Warwick and a member of the center DIMAP there.

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