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.