Leveraging Tree Automata Approximation Results for Efficient Sampling and Counting

Explore efficient sampling and counting techniques for Boolean circuits in this 38-minute lecture by Marcelo Arenas from PUC Chile and RelationalAI. Delve into the challenges of counting satisfying assignments and sampling these assignments in Boolean circuits, and discover how recent advancements in tree automata approximation can be applied to develop polynomial-time approximation algorithms for structured DNNF circuits. Learn about the intersection of probabilistic circuits and logic, and gain insights into innovative approaches for tackling fundamental problems in computer science and artificial intelligence.

Leveraging tree automata approximation results for efficient sampling and counting...