research
∙
06/01/2023
Bounds on BDD-Based Bucket Elimination
We study BDD-based bucket elimination, an approach to satisfiability tes...
share
research
∙
04/12/2023
Skyline Operators for Document Spanners
When extracting a relation of spans (intervals) from a text document, a ...
research
∙
03/09/2022
No Efficient Disjunction or Conjunction of Switch-Lists
It is shown that disjunction of two switch-lists can blow up the represe...
research
∙
01/07/2022
Tight Fine-Grained Bounds for Direct Access on Join Queries
We consider the task of lexicographic direct access to query answers. Th...
research
∙
12/23/2021
Lower Bounds on Intermediate Results in Bottom-Up Knowledge Compilation
Bottom-up knowledge compilation is a paradigm for generating representat...
research
∙
12/02/2021
A short note on the counting complexity of conjunctive queries
This note closes a minor gap in the literature on the counting complexit...
research
∙
10/25/2021
A Compilation of Succinctness Results for Arithmetic Circuits
Arithmetic circuits (AC) are circuits over the real numbers with 0/1-val...
research
∙
04/06/2021
Proof Complexity of Symbolic QBF Reasoning
We introduce and investigate symbolic proof systems for Quantified Boole...
research
∙
03/17/2021
Characterizing Tseitin-formulas with short regular resolution refutations
Tseitin-formulas are systems of parity constraints whose structure is de...
research
∙
12/08/2020
On Irrelevant Literals in Pseudo-Boolean Constraint Learning
Learning pseudo-Boolean (PB) constraints in PB solvers exploiting cuttin...
research
∙
11/27/2020
Lower Bounds for Approximate Knowledge Compilation
Knowledge compilation studies the trade-off between succinctness and eff...
research
∙
05/09/2019
Revisiting Graph Width Measures for CNF-Encodings
We consider bounded width CNF-formulas where the width is measured by po...
research
∙
12/22/2018
Enumeration on Trees with Tractable Combined Complexity and Efficient Updates
We give an algorithm to enumerate the results on trees of monadic second...
research
∙
07/24/2018
Constant-Delay Enumeration for Nondeterministic Document Spanners
We consider the information extraction approach known as document spanne...
research
∙
07/11/2018
Knowledge Compilation, Width and Quantification
We generalize many results concerning the tractability of SAT and #SAT o...
research
∙
05/22/2018
QBF as an Alternative to Courcelle's Theorem
We propose reductions to quantified Boolean formulas (QBF) as a new appr...
research
∙
12/24/2017
On tractable query evaluation for SPARQL
Despite much work within the last decade on foundational properties of S...
research
∙
09/18/2017
Enumeration on Trees under Relabelings
We study how to evaluate MSO queries with free variables on trees, withi...
research
∙
05/23/2014
Understanding model counting for β-acyclic CNF-formulas
We extend the knowledge about so-called structural restrictions of #SAT ...
research
∙
01/24/2014