Abstract
Counting the number of satisfying assignments and sampling these assignments are two fundamental problems for Boolean circuits. Unfortunately, these problems are hard to solve, and even to approximate. On the other hand, the corresponding problems for tree automata have recently been proved to be efficiently approximable. In this talk, we will demonstrate how these results for tree automata can be leveraged to derive polynomial-time approximation algorithms for the counting and sampling problems for structured DNNF circuits.