• Classified by Research Topic • Sorted by Date • Classified by Publication Type •
INC: A Scalable Incremental Weighted Sampler.
Suwei Yang, and Kuldeep S. Meel.
In Proceedings of Formal Methods in Computer-Aided Design (FMCAD), October 2022.
The fundamental problem of weighted sampling involves sampling of satisfying assignments of Boolean formulas, which specify sampling sets, and according to distributions defined by pre-specified weight functions to weight functions. The tight integration of sampling routines in various applications has highlighted the need for samplers to be incremental, i.e., samplers are expected to handle updates to weight functions. The primary contribution of this work is an efficient knowledge compilation-based weighted sampler, INC, designed for incremental sampling. INC builds on top of the recently proposed knowledge compilation language, OBDD[AND], and is accompanied by rigorous theoretical guarantees. Our extensive experiments demonstrate that INC is faster than state-of-the-art approach for majority of the evaluation. In particular, we observed a median of 1.69X runtime improvement over the prior state-of-the-art approach
@inproceedings{YM22,
author={Yang, Suwei and Meel, Kuldeep S.},
title={INC: A Scalable Incremental Weighted Sampler},
bib2html_pubtype={Refereed Conference},
year={2022},
month=oct,
booktitle=FMCAD,
bib2html_rescat={Sampling},
bib2html_dl_pdf={../Papers/fmcad22.pdf},
abstract={
The fundamental problem of weighted sampling involves sampling of satisfying
assignments of Boolean formulas, which specify sampling sets, and according
to distributions defined by pre-specified weight functions to weight
functions. The tight integration of sampling routines in various
applications has highlighted the need for samplers to be incremental, i.e.,
samplers are expected to handle updates to weight functions.
The primary contribution of this work is an efficient knowledge
compilation-based weighted sampler, INC, designed for incremental sampling.
INC builds on top of the recently proposed knowledge compilation language,
OBDD[AND], and is accompanied by rigorous theoretical guarantees. Our
extensive experiments demonstrate that INC is faster than state-of-the-art
approach for majority of the evaluation. In particular, we observed a median
of 1.69X runtime improvement over the prior state-of-the-art approach
},
}
Generated by bib2html.pl (written by Patrick Riley with layout from Sanjit A. Seshia ) on Tue Apr 28, 2026 01:27:21