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

Abstract

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 domainliftability 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 (sic)x(sic)=ky : phi(x, y) and (sic) =(kappa)x(sic)y : phi(x, y), for some quantifierfree formula phi(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.