• 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 Sun Apr 14, 2024 11:15:51