Information

Event Records

11th CoRe Seminar

Date and time:  2021.06.07 Mon. 10:00-12:00
Venue:  Online
Speaker:  IWAMASA, Yuni (Kyoto U., Group C01)
Title:  An algebraic approach to constraint satisfaction problems
Summary: 
The constraint satisfaction problem (CSP) is the problem of determining if there exists an assignment of values to variables so that all given constraints are satisfied. While the CSP is NP-complete in general, a restriction on relations appearing in constraints can ensure the polynomial-time solvability. In 1998, Feder and Vardi conjectured that a problem obtained from such a restriction is either in P or NP-complete, which is called the dichotomy conjecture. This was settled affirmatively by Bulatov and by Zhuk in 2017. In this talk, I will give a brief overview of an algebraic approach to CSPs that plays an important role in the proofs of the dichotomy conjecture.
Update:2021.05.25