On Relaxing Determinism in Arithmetic Circuits
  The past decade has seen a significant interest in learning tractable
probabilistic representations. Arithmetic circuits (ACs) were among the first
proposed tractable representations, with some subsequent representations being
instances of ACs with weaker or stronger properties. In this paper, we provide
a formal basis under which variants on ACs can be compared, and where the
precise roles and semantics of their various properties can be made more
transparent. This allows us to place some recent developments on ACs in a
clearer perspective and to also derive new results for ACs. This includes an
exponential separation between ACs with and without determinism; completeness
and incompleteness results; and tractability results (or lack thereof) when
computing most probable explanations (MPEs).
