3 citations · 6 across the 4 of their papers we have counts for
11 papers
Promise Constraint Satisfaction and Width
Albert Atserias, Víctor Dalmau
We study the power of the bounded-width consistency algorithm in the context of the fixed-template Promise Constraint Satisfaction Problem (PCSP). Our main technical finding is tha…
On the Expressive Power of Homomorphism Counts
Albert Atserias, Phokion G. Kolaitis, Wei-Lin Wu
A classical result by Lovász asserts that two graphs and are isomorphic if and only if they have the same left profile, that is, for every graph , the number of homomorp…
Structure and Complexity of Bag Consistency
Albert Atserias, Phokion G. Kolaitis
Since the early days of relational databases, it was realized that acyclic hypergraphs give rise to database schemas with desirable structural and algorithmic properties. In a by-n…
Clique Is Hard on Average for Regular Resolution
Albert Atserias, Ilario Bonacina, Susanna F. de Rezende +3
We prove that for regular resolution requires length to establish that an Erdős-Rényi graph with appropriately chosen edge density does not contain a…
Consistency, Acyclicity, and Positive Semirings
Albert Atserias, Phokion G. Kolaitis
In several different settings, one comes across situations in which the objects of study are locally consistent but globally inconsistent. Earlier work about probability distributi…
Automating Resolution is NP-Hard
Albert Atserias, Moritz Müller
We show that the problem of finding a Resolution refutation that is at most polynomially longer than a shortest one is NP-hard. In the parlance of proof complexity, Resolution is n…