Efficient Enumeration Algorithms via Circuits

Explore a 44-minute lecture on efficient enumeration algorithms using circuits, presented by Antoine Amarili from Telecom Paris at the Simons Institute. Delve into the results of efficiently enumerating satisfying assignments of circuits in tractable knowledge compilation formalisms, including structured d-DNNFs and their variants. Discover how these findings can be applied to re-prove linear-preprocessing and output-linear delay enumeration of satisfying assignments in Monadic Second-Order logic queries on trees, as well as the enumeration of document spanner mappings in database theory. Learn about the implications of these results for efficient updates to underlying circuits, leading to advancements in maintaining enumeration structures on dynamic data. Gain insights into the intersection of probabilistic circuits and logic in this comprehensive talk from the "Probabilistic Circuits and Logic" series.