activity
20112023
most citedUnifying the Three Algebraic Approaches to the CSP via Minimal Taylor Algebras

6 citations · 20 across the 15 of their papers we have counts for

collaborators
Showing 2017Show all

2 papers · 1 filter

cs.CC2017

A Proof of the CSP Dichotomy Conjecture

Dmitriy Zhuk

Many natural combinatorial problems can be expressed as constraint satisfaction problems. This class of problems is known to be NP-complete in general, but certain restrictions on…

cs.LO2017★ 1 cited

The complexity of quantified constraints using the algebraic formulation

Catarina Carvalho, Barnaby Martin, Dmitriy Zhuk

Let A be an idempotent algebra on a finite domain. We combine results of Chen, Zhuk and Carvalho et al. to argue that if A satisfies the polynomially generated powers property (PGP…