Return to Colloquia & Seminar listing
Exact sampling of combinatorial structures
Algebra & Discrete Mathematics| Speaker: | Stephen de Salvo, UCLA |
| Location: | 1147 MSB |
| 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.