What are bounded-treewidth circuits good for?

Question

One can talk of the treewidth of a Boolean circuit, defining it as the treewidth of the "moralized" graph on wires (vertices) obtained as follows: connect wires $a$ and $b$ whenever $b$ is the output of a gate having $a$ as input (or vice-versa); connect wires $a$ and $b$ whenever they are used as inputs to the same gate. Edit: one can equivalently define the treewidth of the circuit as that of the graph representing it; if we use associativity to rewite all AND and OR gates to have fan-in at most two, the treewidth according to either definition is the same up to a factor $3$.

There is at least one problem that is known to be untractable in general but tractable on Boolean circuits of bounded treewidth: given a probability for each of the input wires to be set to 0 or 1 (independently from the others), compute the probability that a certain output gate is 0 or 1. This is generally #P-hard by a reduction from e.g. #2SAT, but it can be solved in PTIME on circuits whose treewidth is assumed to be less than a constant, using the junction tree algorithm.

My question is to know whether there are other problems, beyond probabilistic computation, that are known to be intractable in general but tractable for bounded-treewidth circuts, or whose complexity can be described as a function of the circuit size and also of its treewidth. My question is not specific to the Boolean case; I am also interested in arithmetic circuits over other semirings. Do you see any such problems?

Answer 1

We now understand that for any fixed bound $k \in \mathbb{N}$ on the treewidth, we can convert any Boolean circuit of treewidth less than $k$ to a so-called d-SDNNF circuit, in linear time and with the dependency on $k$ being singly exponential.

The so-called d-SDNNFs are circuits satisfying conditions on the use of negation (only at the leaves), determinism (the inputs to OR-gates are mutually exclusive), decomposability (the inputs to AND-gates depend on disjoint sets of variables), and stucturedness (the AND-gates split the variables in some fixed way throughout the circuit, as described by a v-tree). This class has been studied in knowledge compilation and is known to enjoy tractable SAT and tractable model counting (recapturing probabilistic evaluation and counting), but other problems have been studied for this class such as enumeration, quantification, etc.

So one way to use bounds on the treewidth of a circuit is to convert it to this d-SDNNF class which has more explicit properties in terms of the circuit semantics, and for which there are several known results on the tractability of various tasks.