CSPs and Symmetries

Abstract: How difficult is to solve a given computational problem? In a large class of computational problems, including the fixed-template Constraint Satisfaction Problems (CSPs), this fundamental question has a simple and beautiful answer: the more symmetrical the problem is, the easier is to solve it. The tight connection between the complexity of a CSP and a certain concept that captures its symmetry has fueled much of the progress in the area in the last 20 years. I will talk about this connection and some of the many tools that have been used to analyze the symmetries. The tools involve rather diverse areas of mathematics including algebra, analysis, combinatorics, logic, probability, and topology.

group theory

Audience: researchers in the discipline

Symmetry in Newcastle