This is joint work with David Richerby.

Andrei Bulatov showed that # CSP has a dichotomy, using methods from universal algebra. We will describe a simpler proof of the result, based on succinct representations for a certain class of relations, similar to one described by Bulatov and Dalmau. This leads to a new criterion for the dichotomy, which differs from Bulatov’s, but can be shown to be equivalent to it. The advantage of the new criterion is that it leads to a decision procedure for the dichotomy, a major question left open by Bulatov. The talk will conclude with an outline of this decision algorithm.