79 citations · 93 across the 20 of their papers we have counts for
Showing 2020Show all
3 papers · 1 filter
cs.DB2020
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…
cs.CC2020
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…
cs.DB2020★ 1 cited
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…