Symbolic Uniform Sampling with XOR Circuits
Journal
IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
Journal Volume
2020-November
Date Issued
2020
Author(s)
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. ? 2020 Association on Computer Machinery.
Subjects
Computer aided design; Sampling; Timing circuits; Algorithm design; Biased sampling; Boolean reasoning; Model Counting; Sampling circuits; Symbolic representation; System verifications; Uniform sampling; Importance sampling
Type
conference paper