Mathematics Colloquia and Seminars

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.