Tractable Operations for Arithmetic Circuits of Probabilistic Models
We consider tractable representations of probability distributions and the polytime operations they support. In particular, we consider a recently proposed arithmetic circuit representation, the Probabilistic Sentential Decision Diagram (PSDD). We show that PSDDs support a polytime multiplication operator, while they do not support a polytime operator for summing-out variables. A polytime multiplication operator makes PSDDs suitable for a broader class of applications compared to classes of arithmetic circuits that do not support multiplication. As one example, we show that PSDD multiplication leads to a very simple but effective compilation algorithm for probabilistic graphical models: represent each model factor as a PSDD, and then multiply them.
The authors describe algorithms for operations on arithmetic circuits suitable for representing probability distributions. Such circuits can be used as a sparse and efficient representation for probability distributions, therefore the manuscript has high potential impact for practical applications in probabilistic reasoning and fits NIPS.  Concretely the authors work on PSDDs (probabilistic sentential decision diagrams) and describe theoretical results on multiplying such representations, compiling PSDDs into arithmetic circuits, multiplying two PSDDs, summing out probabilities, several representation results and an empirical comparison with other approaches.
The manuscript advances the theoretical framework of PSDDs and contains contributions that can make applications on probabilistic representations more efficient in the future.  The only drawback of the manuscript is, that it is not self- contained and requires background reading to intuitively understand, because the example (figures) are not explained in detailed and because some preliminaries are not given.  Nevertheless I recommend acceptance for publication.  Detailed drawbacks of examples: * Figure 1 shows a circuit for a network A -> B   and it contains numbers attached to nodes,   however it is not clear what these numbers are,   and how they are related to A -> B. Also the text   does not explain this.   From my interpretation, this is just an arbitrary   example situation, where \theta_a = 0.3, ...   Curiously, \lambda_b = 1 and \lambda_\not{b} = 1   although these should be inverse if they are indicators.    It does not help that Figure 1 and Figure 2 seem to   describe two complete distinct examples (Fig 2 has 3 variables,   Fig 1 has only two). * Figure 2 shows several numbers (1, 1, 3, 4) that are   not intuitive. In (b) and (c) they are attached to the    topologically same or-gates, however in (d) in addition   there is "0" and "2", and only one "1". I recommend to revise the presentation of these examples, putting the figures later (to the text that describes it) and perhaps putting the figures on separate pages because they seem to be unrelated.  (I wonder if the and/or gate way of drawing PSDDs is a good choice, as drawing them just as graphs with edge labels would be more close to the original ACs, however this seems to be a choice of the authors of previous papers.)  Minor comments: * 18: compilating -> compiling * Figure 4: top-aligning the three trees could be nicer * Table 1: winning (shortest) times could be marked in bold * Table 1: what is the unit of size? not MB as it seems. nodes?