Symbolic Uniform Sampling with XOR Circuits

Abstract

Uniform sampling is an important method in statistics and has various applications in model counting, system verification, algorithm design, among others. Symbolic sampling in a Boolean space is a recently proposed technique that combines sampling and symbolic representation for effective Boolean reasoning. Under the framework of symbolic sampling, we propose a method to construct compact XOR circuits achieving uniform sampling in a given Boolean space. The method is further extended to biased sampling within a focused subspace of interest. Experimental results show the effectiveness of compact sampling circuit generation and its potential to facilitate Boolean reasoning.