16 citations · 17 across the 3 of their papers we have counts for
5 papers
On the Power of Symmetric Linear Programs
Albert Atserias, Anuj Dawar, Joanna Ochremiak
We consider families of symmetric linear programs (LPs) that decide a property of graphs (or other relational structures) in the sense that, for each size of graph, there is an LP…
Definable isomorphism problem
Khadijeh Keshvardoost, Bartek Klin, Sławomir Lasota +2
We investigate the isomorphism problem in the setting of definable sets (equivalent to sets with atoms): given two definable relational structures, are they related by a definable…
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…
Eliminating Recursion from Monadic Datalog Programs on Trees
Filip Mazowiecki, Joanna Ochremiak, Adam Witkowski
We study the problem of eliminating recursion from monadic datalog programs on trees with an infinite set of labels. We show that the boundedness problem, i.e., determining whether…
Algebraic Properties of Valued Constraint Satisfaction Problem
Marcin Kozik, Joanna Ochremiak
The paper presents an algebraic framework for optimization problems expressible as Valued Constraint Satisfaction Problems. Our results generalize the algebraic framework for the d…