2014
2015
2016
2017
2018

The thirty-fourth meeting of the Prague computer science seminar

Libor Barto

Symmetry in Computational Complexity

The rapid progress in computational-theoretic aspects of the fixed-language Constraint Satisfaction Problems during the last 20 years has been fueled by the connection between their computational complexity and a certain concept that captures the symmetry of Constraint Satisfaction Problems.

March 22, 2018

4:00pm

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

Lecture annotation

The rapid progress in computational-theoretic aspects of the fixed-language Constraint Satisfaction Problems during the last 20 years has been fueled by the connection between their computational complexity and a certain concept that captures the symmetry of Constraint Satisfaction Problems.

I will talk about this connection and my vision that it would eventually evolve into the organizing principle of computational complexity and would lead to solutions of fundamental problems such as the Unique Games Conjecture or even the P-versus-NP problem.

Lecturer

Libor Barto

Libor Barto is an associate professor at the Department of Algebra, Charles University. His scientific interests include universal algebra and computational complexity, in particular, constraint satisfaction problems. He is best known for introducing the absorption theory, which has led to, e.g., the characterization of problems solvable by local methods. He is the recipient of the ERC Consolidator grant Symmetry in computational complexity. He obtained Ph.D. from Charles University in 2006. From 2010 to 2012 he worked at McMaster University in Canada.

ABOUT THE PRAGUE COMPUTER SCIENCE SEMINAR

The seminar takes place usually 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 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 (Czech Tech. Univ., Faculty of Information Technologies), Michal Koucký (Charles University, Faculty of Mathematics and Physics), 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