On the Hardness of Approximating Distributions with Tractable Probabilistic Models
Published in NeurIPS, 2025
TLDR: We investigate the hardness of approximating distributions with TPMs. Our main results show the NP-hardness of approximation with a bounded f-divergence for any model which can tractably marginalize, and an exponential lower bound on the size of a deterministic, decomposable probabilisitic circuit representing a distribution exactly encoded by a decomposable probabilistic circuit. We also have a number of results related to bounded f-divergence and approximate inference guarantees.