CTU Events

Prague Computer Science Seminar - Prof. Daniel Kráľ - Mathematics and fast algorithms

23 Oct 2014   16:00

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.

LECTURER

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.

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.

ABOUT THE PRAGUE COMPUTER SCIENCE SEMINAR

The seminar will take 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 will consist of a one-hour lecture followed by a discussion. The lecture should be 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 will be in English.

Place

ČVUT FEL Karlovo nám. 13, budova E, KN:E-107 Zengerova posluchárna

Organizer

Přípravný výbor PIS

Contact person

Přípravný výbor PIS, info@praguecomputerscience.cz

More information

http://www.praguecomputerscience.cz/

Attachment

Download