Theory Seminar

Friday, April 19, 2019 - 3:00pm to 4:00pm


Reddy Conference Room 4405 Gates Hillman Centers


JAKUB OPRĊ AL, Post-doctoral Associate

Approximate graph coloring, polymorphisms, and identities

It is well-known that finding a 3-coloring of a given graph that is promised to be 3-colorable is NP-complete. One might be interested in a relaxed version of this problem, e.g. finding a coloring of a 3-colorable graph that uses k colors for some fixed k > 3. This falls into a more general scope of so-called promise constraint satisfaction problem (PCSP). A template of PCSP is a pair of relational structures A and B (e.g. two graphs) with a homomorphism from A to B, the goal is, given a similar structure that is promised to map to A by a homomorphism, find a homomorphism to B.

We will talk about a general theory giving some abstract tools to attack the complexity of the problems of this sort. This is based on so-called algebraic approach to constraint satisfaction problem (CSP) that was one of the essential tools in the recent resolution the P vs. NP-complete dichotomy of the non-uniform CSP. We will also show how can be these abstract tools used to provide new results on the aforementioned approximate graph coloring.

No familiarity with CSP dichotomy or associated algebraic approach will be assumed.

Faculty Host: Venkatesan Guruswami

Event Website:

For More Information, Contact:


Seminar Series