doc. Mgr. Libor Barto, Ph.D. presents 34. Prague Computer Science Seminar

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 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.