Abstract
Arithmetic circuits, or AC, are circuits with 0/1-valued input variables, that output real numbers, and whose gates compute the weighted sum or the product of their inputs. AC subsume several interesting probabilistic models but, under standard complexity-theoretic assumptions, many operations useful in probabilistic reasoning are intractable when the distribution is given as an AC. Efficient polynomial-time algorithms for these operations become available when imposing to the AC structural restrictions such as decomposability, determinism, smoothness, etc. However the structural restrictions often increase dramatically the size of these "tractable" AC. In this talk, we describe techniques to prove lower bounds on the size of tractable AC. We outline the different variants depending on the structural restrictions and we give an example of application with a function that can only be represented by large structured-decomposable AC.