Papers › On Exact Sampling in the Two-Variable Fragment of First-Order Logic
On Exact Sampling in the Two-Variable Fragment of First-Order Logic
Yuanhong Wang, Juhua Pu, Yuyi Wang, Ondřej Kuželka
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 𝐅𝐎² (𝐔𝐅𝐎²) to the entire fragment of 𝐅𝐎². Specifically, we prove the domain-liftability under sampling of 𝐅𝐎², meaning that there exists a sampling algorithm for 𝐅𝐎² 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 ∀x∃₌ₖ y: φ(x,y) and ∃₌ₖ x∀y: φ(x,y), for some quantifier-free formula φ(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.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections