@COMMENT This file was generated by bib2html.pl <https://sourceforge.net/projects/bib2html/> version 0.94
@COMMENT written by Patrick Riley <http://sourceforge.net/users/patstg/>
@COMMENT This file came from Kuldeep S. Meel's publication pages at
@COMMENT http://www.comp.nus.edu.sg/~meel/publications/
@inproceedings{SGRM18,
  author={
    Sharma, Shubham and Gupta, Rahul and Roy, Subhajit and Meel, Kuldeep S.
  },
  title={Knowledge Compilation meets Uniform Sampling},
  year={2018},
  bib2html_pubtype={Refereed Conference},
  code={https://github.com/meelgroup/KUS},
  bib2html_dl_pdf={../Papers/lpar18.pdf},
  booktitle=LPAR,
  month=nov,
  bib2html_rescat={Sampling},
  abstract={
    Uniform sampling has drawn diverse applications in programming languages and
    software engineering, like in constrained-random verification (CRV),
    constrained-fuzzing and bug synthesis. The effectiveness of these
    applications depend on the uniformity of test stimuli generated from a given
    set of constraints. Despite significant progress over the past few years,
    the performance of the state of the art techniques still falls short of
    those of heuristic methods employed in the industry which sacrifice either
    uniformity or scalability when generating stimuli.
    In this paper, we propose a new approach to the uniform generation that
    builds on recent progress in knowledge compilation. The primary contribution
    of this paper is marrying knowledge compilation with uniform sampling: our
    algorithm, KUS, employs the state-of-the-art knowledge compilers to first
    compile constraints into d-DNNF form, and then, generates samples by making
    two passes over the compiled representation.
    We show that KUS is able to significantly outperform existing
    state-of-the-art algorithms, SPUR and UniGen2, by up to 3 orders of
    magnitude in terms of runtime while achieving a geometric speedup of 1.7 and
    8.3 over SPUR and UniGen2 respectively. Also, KUS achieves a lower PAR-2
    score, around 0.82x that of SPUR and 0.38x that of UniGen2. Furthermore, KUS
    achieves speedups of up to 3 orders of magnitude for incremental sampling.
    The distribution generated by KUS is statistically indistinguishable from
    that generated by an ideal uniform sampler. Moreover, KUS is almost
    oblivious to the number of samples requested.
  },
}