17 citations · 34 across the 18 of their papers we have counts for
3 papers · 1 filter
When do homomorphism counts help in query algorithms?
Balder ten Cate, Víctor Dalmau, Phokion G. Kolaitis +1
A query algorithm based on homomorphism counts is a procedure for determining whether a given instance satisfies a property by counting homomorphisms between the given instance and…
Multi-Structural Games and Beyond
Marco Carmosino, Ronald Fagin, Neil Immerman +3
Multi-structural (MS) games are combinatorial games that capture the number of quantifiers of first-order sentences. On the face of their definition, MS games differ from Ehrenfeuc…
Generalized Satisfiability Problems via Operator Assignments
Albert Atserias, Phokion G. Kolaitis, Simone Severini
Schaefer introduced a framework for generalized satisfiability problems on the Boolean domain and characterized the computational complexity of such problems. We investigate an alg…