Abstract
We give a Markov chain based perfect sampler for uniform sampling solutions of constraint satisfaction problems (CSP). Under some mild Lovász local lemma conditions where each constraint has a small number of forbidden local configurations, our algorithm is accurate and efficient: it outputs a perfect uniform random solution of the CSP and its expected running time is quasilinear in the number of variables of the CSP. Prior to our work, perfect samplers are only shown to exist for CSPs under much more restrictive conditions (Guo, Jerrum, and Liu, JACM'19).
Our algorithm is a natural combination of bounding chains (Huber, STOC'98; Haggstrom and Nelander, Scandinavian Journal of Statistics'99) and state compression (Feng, He, and Yin, STOC'21). The crux of our analysis is a simple information percolation argument which still allows us to achieve bounds obtained by current best approximate samplers (Jain, Pham, and Vuong, ArXiv'21).
Previous related works either use intricate algorithms or needs sophisticated analysis or even both. Thus we view the simplicity of both our algorithm and analysis as a strength of our work.
Joint work with Kun He and Xiaoming Sun.
Time
2021-06-19 11:30-12:00Speaker
Room
Guangdong Hotel Shanghai
