5 papers
Proof complexity of Mal'tsev CSP
Azza Gaysin
Constraint Satisfaction Problems (CSPs) form a broad class of combinatorial problems, which can be formulated as homomorphism problems between relational structures. The CSP dichot…
Proof complexity of universal algebra in a CSP dichotomy proof
Azza Gaysin
The constraint satisfaction problem (CSP) can be formulated as a homomorphism problem between relational structures: given a structure , for any structure $\mathcal{X}…
Proof complexity of CSP
Azza Gaysin
The CSP (constraint satisfaction problems) is a class of problems deciding whether there exists a homomorphism from an instance relational structure to a target one. The CSP dichot…
Block-groups and Hall relations
Azza M. Gaysin, Mikhail V. Volkov
A binary relation on a finite set is called a Hall relation if it contains a permutation of the set. Under the usual relational product, Hall relations form a semigroup which is kn…
H-coloring Dichotomy in Proof Complexity
Azza Gaysin
The -coloring problem for undirected simple graphs is a computational problem from a huge class of the constraint satisfaction problems (CSP): an -colorin…