6 citations · 17 across the 15 of their papers we have counts for
3 papers · 1 filter
Structure-Aware Lower Bounds and Broadening the Horizon of Tractability for QBF
Johannes K. Fichte, Robert Ganian, Markus Hecher +2
The QSAT problem, which asks to evaluate a quantified Boolean formula (QBF), is of fundamental interest in approximation, counting, decision, and probabilistic complexity and is al…
Quantified Conjunctive Queries on Partially Ordered Sets
Simone Bova, Robert Ganian, Stefan Szeider
We study the computational problem of checking whether a quantified conjunctive query (a first-order sentence built using only conjunction as Boolean connective) is true in a finit…
Model Checking Existential Logic on Partially Ordered Sets
Simone Bova, Robert Ganian, Stefan Szeider
We study the problem of checking whether an existential sentence (that is, a first-order sentence in prefix form built using existential quantifiers and all Boolean connectives) is…