7 citations · 11 across the 4 of their papers we have counts for
4 papers
On the relative power of reduction notions in arithmetic circuit complexity
Christian Ikenmeyer, Stefan Mengel
We show that the two main reduction notions in arithmetic circuit complexity, p-projections and c-reductions, differ in power. We do so by showing unconditionally that there are po…
Lower Bounds on the mim-width of Some Graph Classes
Stefan Mengel
mim-width is a recent graph width measure that has seen applications in graph algorithms and problems related to propositional satisfiability. In this paper, we show linear lower b…
A Strongly Exponential Separation of DNNFs from CNF Formulas
Simone Bova, Florent Capelli, Stefan Mengel +1
Decomposable Negation Normal Forms (DNNFs) are Boolean circuits in negation normal form where the subcircuits leading into each AND gate are defined on disjoint sets of variables.…
A Trichotomy in the Complexity of Counting Answers to Conjunctive Queries
Hubie Chen, Stefan Mengel
Conjunctive queries are basic and heavily studied database queries; in relational algebra, they are the select-project-join queries. In this article, we study the fundamental probl…