2014
2015
2016
2017

The first meeting of the Prague computer science seminar

Pavel Pudlák

Complexity and Infinity

When the set theory was axiomatized, the guiding principle was to keep as many properties of finite sets as possible also for infinite sets. Today, lacking methods to solve problems in complexity theory...

January 23, 2014

4:00pm

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

Lecture annotation

When the set theory was axiomatized, the guiding principle was to keep as many properties of finite sets as possible also for infinite sets. Today, lacking methods to solve problems in complexity theory, we are, in a sense, doing the opposite: we make conjectures about finite structures using facts that are true about similar infinite structures. For example, our belief that P ≠ NP is mainly supported by the fact that recursively enumerable sets are not recursive.

I will give some examples of such conjectures in complexity theory and mention some results that can be viewed as corroboration of their validity. These examples come from proof complexity – a field that studies complexity from the perspective of logic – but these conjectures can also be stated in purely computational terms. One of the conjectures is that there is no complete problem for a certain class of search problems.

Lecturer

Prof. RNDr. Pavel Pudlák, DrSc.

Prof. RNDr. Pavel Pudlák, DrSc., is a leading scientist in the field of mathematical logic and theoretical computer science. His research is motivated by fundamental questions like the P=NP problem. His main topics of interest include proof complexity and related areas of complexity theory, combinatorics and algebra. He works at the Institute of Mathematics of the Academy of Sciences of the Czech Republic. His seminars in logic and complexity theory at the Institute have been formative for a number of accomplished mathematicians and computer scientists. He worked at a number of foreign universities and institutes, including the Institute for Advanced Study in Princeton. He has been invited to lecture at outstanding universities and conferences, e.g., at the prestigious International Congress of Mathematicians.

As the first member of the Czech computer science community, he was awarded an ERC Advanced Grant, starting on Jan. 1, 2014, and devoted to theoretical aspects of complexity theory.

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