Title: Promise Constraint Satisfaction Problem

Abstract: What kind of mathematical structure in computational problems
allows for efficient algorithms? This fundamental question now has a
satisfactory answer for a rather broad class of computational problems, so
called fixed-language Constraint Satisfaction Problems (CSPs) - it has
turned out that their complexity is captured by a certain specific form of
symmetry.
I will give examples of CSPs, explain the connection to symmetries, and
briefly discuss some of the major results and research directions. The
second part will focus on recent developments in one of these directions,
the promise CSPs, which include problems such as finding an l-coloring of a
k-colorable (hyper-) graph.