# On Exact Sampling in the Two-Variable Fragment of First-Order Logic

arXiv: https://arxiv.org/abs/2302.02730 · HTML: https://mlsanity.com/paper/2302.02730/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 36 references that are in the map.
- First posted on arXiv 6 Feb 2023.

## Builds on (most cited first, 13 of 13)

- [Symmetric Weighted First-Order Model Counting](https://mlsanity.com/paper/1412.1505/) (2014)
- [Weighted First-Order Model Counting in the Two-Variable Fragment With Counting Quantifiers](https://mlsanity.com/paper/2007.05619/) (2020)
- [Skolemization for Weighted First-Order Model Counting](https://mlsanity.com/paper/1312.5378/) (2013)
- [New Liftable Classes for First-Order Probabilistic Inference](https://mlsanity.com/paper/1610.08445/) (2016)
- [Weighted model counting beyond two-variable logic](https://mlsanity.com/paper/1804.10185/) (2018)
- [Lifted Inference with Linear Order Axiom](https://mlsanity.com/paper/2211.01164/) (2022)
- [A Scalable and Nearly Uniform Generator of SAT Witnesses](https://mlsanity.com/paper/1304.1584/) (2013)
- [Uniform Sampling through the Lov'asz Local Lemma](https://mlsanity.com/paper/1611.01647/) (2016)
- [Domain Recursion for Lifted Inference with Existential Quantifiers](https://mlsanity.com/paper/1707.07763/) (2017)
- [Sampling Constraint Satisfaction Solutions in the Local Lemma Regime](https://mlsanity.com/paper/2011.03915/) (2020)
- [On the Complexity and Approximation of Binary Evidence in Lifted Inference](https://mlsanity.com/paper/1311.6591/) (2013)
- [Uniform generation of random regular graphs](https://mlsanity.com/paper/1511.01175/) (2015)
- [Perfect Sampling for (Atomic) Lov'asz Local Lemma](https://mlsanity.com/paper/2107.03932/) (2021)

## Built on by (most cited first, 3 of 3)

- [Lifted Algorithms for Symmetric Weighted First-Order Model Sampling](https://mlsanity.com/paper/2308.08828/) (2023)
- [Bridging Weighted First Order Model Counting and Graph Polynomials](https://mlsanity.com/paper/2407.11877/) (2024)
- [Model Enumeration of Two-Variable Logic with Quadratic Delay Complexity](https://mlsanity.com/paper/2505.19648/) (2025)

## Abstract (arXiv)

In this paper, we study the sampling problem for first-order logic proposed recently by Wang et al. -- how to efficiently sample a model of a given first-order sentence on a finite domain? We extend their result for the universally-quantified subfragment of two-variable logic FO2 (UFO2) to the entire fragment of FO2. Specifically, we prove the domain-liftability under sampling of FO2, meaning that there exists a sampling algorithm for FO2 that runs in time polynomial in the domain size. We then further show that this result continues to hold even in the presence of counting constraints, such as forall xexists=k y: varphi(x,y) and exists=k xforall y: varphi(x,y), for some quantifier-free formula varphi(x,y). Our proposed method is constructive, and the resulting sampling algorithms have potential applications in various areas, including the uniform generation of combinatorial structures and sampling in statistical-relational models such as Markov logic networks and probabilistic logic programs.