Prague computer science seminar: Libor Barto - Symmetry in Computational Complexity
Date: 22/03/2018 16:00
Place: Auditorium E-301, FEL CTU Karlovo nám. 13, Praha 2
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
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.
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
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.