2014
2015
2016
2017

The eighteenth meeting of the Prague computer science seminar

Michal Koucký

Lower bounds and the physical reality

Algorithms provide bounds (upper bounds) on the amount of resources such as time and space that suffice to solve various computational problems. On the other hand, lower bounds provide bounds on the amount of resources that are necessary to solve such problems.

January 28, 2016

4:00pm

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

Lecture annotation

Algorithms provide bounds (upper bounds) on the amount of resources such as time and space that suffice to solve various computational problems. On the other hand, lower bounds provide bounds on the amount of resources that are necessary to solve such problems. Together they allow us to recognize what is the best possible algorithm for the given problem.

In this talk I will survey our progress in proving lower bounds, and I will illustrate how these questions are related to some fundamental problems studied in physics. I will demonstrate some of the obstacles that we face when proving lower bounds on the example of catalytic computation. Catalytic computation is a novel way of using occupied space (memory) to carry out useful computation.

Lecturer

Michal Koucký

Michal Koucký works in theoretical computer science where he focuses on computational complexity, data structures, and combinatorics. He is best known for introducing exploration sequences, his work on parallel random walks, and various lower bounds. He is the recepient of the ERC Consolidator grant Lower bounds for combinatorial algorithms and dynamic problems. He obtained Ph.D. from Rutgers University. Afterwards he worked at the Mathematical Institute of the Academy of Sciences of the Czech Republic and at the universities in Austin, Montreal, Amsterdam, Toronto and Aarhus. Since 2013 he is a member of the Computer Science Institute of Charles University in Prague.

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