Exact sampling of combinatorial structuresAlgebra & Discrete Mathematics
|Speaker:||Stephen de Salvo, UCLA|
|Start time:||Mon, Apr 18 2016, 4:10PM|
In this talk, we will discuss a general method for exact sampling of combinatorial structures called probabilistic divide-and-conquer (PDC). Examples of applications include integer partitions, contingency tables, latin squares, set partitions. One variation of the method, ``PDC deterministic second half,” provides an immediate improvement to exact Boltzmann samplers; another variation, ``self-similar PDC,” requires more detailed knowledge of the underlying structure, and has been utilized to obtain asymptotically efficient sampling algorithms.