7 citations · 11 across the 4 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2016
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…
cs.CC2014★ 2 cited
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.…
cs.CC2014★ 7 cited
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…