Compiling FO Sentences to Circuits - Upper Bounds and Lower Bounds on the Size of the Circuit

Explore the compilation of Boolean formulas into circuits, focusing on OBDDs, FBDDs, and Decision-DNNFs, in this 49-minute lecture by Dan Suciu from the University of Washington. Delve into the concept of provenance for First Order (FO) sentences over finite domains and examine the optimal circuit size as a function of domain size. Discover a dichotomy theorem for universally quantified, positive FO sentences compiled into OBDDs, and learn about limitations of FBDDs and Decision-DNNFs for certain FO sentences with tractable model counting. Consider the open problem of identifying a circuit class suitable for efficient compilation of all FO sentences with tractable model counting. This talk, part of the Probabilistic Circuits and Logic series at the Simons Institute, presents joint work with Paul Beame, Abhay Jha, Jerry Li, and Sudeepa Roy.

Compiling FO Sentences to Circuits: Upper Bounds and Lower Bounds on the Size of the Circuit