Lower Bounds for Approximate Knowledge Compilation
  Knowledge compilation studies the trade-off between succinctness and
efficiency of different representation languages. For many languages, there are
known strong lower bounds on the representation size, but recent work shows
that, for some languages, one can bypass these bounds using approximate
compilation. The idea is to compile an approximation of the knowledge for which
the number of errors can be controlled. We focus on circuits in deterministic
decomposable negation normal form (d-DNNF), a compilation language suitable in
contexts such as probabilistic reasoning, as it supports efficient model
counting and probabilistic inference. Moreover, there are known size lower
bounds for d-DNNF which by relaxing to approximation one might be able to
avoid. In this paper we formalize two notions of approximation: weak
approximation which has been studied before in the decision diagram literature
and strong approximation which has been used in recent algorithmic results. We
then show lower bounds for approximation by d-DNNF, complementing the positive
results from the literature.
