Conservative dichotomy revisited
Speaker:
Andrei Bulatov, Simon Fraser University
Date and Time:
Wednesday, August 3, 2011 - 11:00am to 12:00pm
Abstract:
The first proof of the Dichotomy conjecture for conservative algebras (2003) introduced colored graphs of relational structures and suggested a very sophisticated solution algorithm for polynomial time problems. The alternative proof of the same result given by Barto in 2011 uses a different approach and presents a significantly simpler algorithm. In this talk we make use of recent developments in the CSP such as the Generalized MajorityMinority algorithm and Maroti’s reduction to simplify dramatically the old proof.