Restructuring Tractable Circuits

Circuits serve as a unifying representation of functions (e.g. probability distributions, Boolean functions, and databases) that support tractable inference. Numerous applications of circuits depend on the ability to efficiently multiply two circuits. Existing algorithms for multiplication require that the circuits respect the same structure, i.e., hierarchical variable decomposition (vtree). In this talk, I will discuss the task of restructuring circuits: that is, transforming a circuit to share the structure of another circuit. I will present a generic approach for this problem and show how it leads to novel polynomial-time algorithms for multiplying circuits, as well as a practical depth-reduction algorithm that improves parallelism in circuit computation.