Perfect Sampling for (Atomic) Lovász Local Lemma (Kewen Wu)

Abstract

We give a Markovchain based perfect sampler for uniform sampling solutions of constraintsatisfaction problems (CSP). Under some mild Lovász local lemma conditions where eachconstraint has a small number of forbidden local configurations, our algorithmis accurate and efficient: it outputs a perfect uniform random solution of theCSP and its expected running time is quasilinear in the number of variables ofthe CSP. Prior to our work, perfect samplers are only shown to exist for CSPs undermuch more restrictive conditions (Guo, Jerrum, and Liu, JACM'19).

Our algorithm is anatural combination of bounding chains (Huber, STOC'98; Haggstrom and Nelander,Scandinavian Journal of Statistics'99) and state compression (Feng, He, andYin, STOC'21). The crux of our analysis is a simple information percolationargument which still allows us to achieve bounds obtained by current best approximatesamplers (Jain, Pham, and Vuong, ArXiv'21).

Previous relatedworks either use intricate algorithms or needs sophisticated analysis or evenboth. Thus we view the simplicity of both our algorithm and analysis as astrength of our work.

Joint work with KunHe and Xiaoming Sun.

Time

2021-06-19  11:30-12:00   

Speaker

Kewen Wu, Universityof California at Berkeley

Room

Guangdong Hotel Shanghai