Uniform Sampling through the Lovász Local Lemma (Heng Guo)

Abstract

We propose a new algorithmic framework, called “partial rejection sampling”, to draw samples exactly from a product distribution, conditioned on none of a number of bad events occurring. Our framework builds (perhaps surprising) new connections between the variable framework of the Lov’asz Local Lemma and some classical sampling algorithms such as the “cycle-popping” algorithm for rooted spanning trees by Wilson. Among other applications, we discover new algorithms to sample satisfying assignments of k-CNF formulas with bounded variable occurrences.

Based on joint work with Mark Jerrum and Jingcheng Liu.

Time

2016-12-21   10:45 ~ 11:30   

Speaker

Heng Guo, Queen Mary, University of London

Room

Room 102, No.100 Wudong Road, School of Information Management & Engineering, Shanghai University of Finance & Economics