79 citations · 93 across the 20 of their papers we have counts for
3 papers · 1 filter
Size bounds and query plans for relational joins
Albert Atserias, Martin Grohe, Dániel Marx
Relational joins are at the core of relational algebra, which in turn is the core of the standard database query language SQL. As their evaluation is expensive and very often domin…
Proof Complexity Meets Algebra
Albert Atserias, Joanna Ochremiak
We analyse how the standard reductions between constraint satisfaction problems affect their proof complexity. We show that, for the most studied propositional, algebraic, and semi…
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…