First-Order Model Counting and Sampling
summary
Describes weighted first‑order model counting (WFOMC) and sampling (WFOMS) for the symmetric case and shows concrete algorithms: reduce richer fragments to universally quantified FO2 via a skolemization that preserves counts (introducing negative-weight predicates), use polynomial interpolation to extract cardinality-constrained counts, and handle counting‑quantifiers by introducing labeled Fi relations with a final division by k! per element. Claims C2 is polynomial‑time in n while FO3 is intractable, implements an OEIS‑style database of sequences from C2 formulas (demo .ninja) and gives a domain recursion sampling procedure that provably works within the tractable fragment.
AI-written summary · about
chapters (8)
- 0:00Introduction to model counting
- 3:50Tractable logic fragments
- 5:56Combinatorial applications
- 10:40Automated sequence database
- 14:58Algorithm design approach
- 21:44First-order model sampling
- 26:05Sampling algorithms and usage
- 30:21Q&A and concluding remarks
related talks
48mProbabilistic Reasoning by First-Order Model Counting
02h 28mIsomorphic Reasoning: Counting with Types Part 2
46mConstrained Sampling and Counting
01h 52mIsomorphic Reasoning: Counting with Types Part 3
01h 39mIsomorphic Reasoning: Counting with Types Part 1
24mHigher order programming with probabilistic effects: A model of stochastic memo...
01h 26mStreaming, Sketching and Sufficient Statistics II
41mCounting Solutions to Random CNF Formulas