Home

Perfect Sampling for (Atomic) Lovász Local Lemma


Speaker

吴克文,University of California at Berkeley

Time

2021-07-12 15:00:00 ~ 2021-07-12 16:30:00

Location

软件大楼专家楼1319会议室

Host

杨宽

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 of the CSP has a small number of forbidden local configurations, our algorithm is accurate and efficient: it outputs a perfect uniform random solution and its expected running time is quasilinear in the number of variables. 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 has two components:

• A simple perfect sampling algorithm using bounding chains (Huber, STOC’98; Haggstrom and Nelander, Scandinavian Journal of Statistics’99).

This sampler is efficient if each variable domain is small.

• A simple but powerful state tensorization trick to reduce large domains to smaller ones.

This trick is a generalization of state compression (Feng, He, and Yin, STOC’21).

The crux of our analysis is a simple information percolation argument which allows us to achieve bounds even beyond 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.

 
Bio

Kewen Wu is a first-year graduate student, supervised by Prof. Avishay Tal, in the theory group of University of California at Berkeley.

Before joining UC Berkeley, he received Bachelor's degree in Computer Science and Math from Peking University.

He has broad interest in theoretical computer science and its connection with mathematics.

 
© John Hopcroft Center for Computer Science, Shanghai Jiao Tong University
分享到

地址:上海市东川路800号上海交通大学软件大楼专家楼
邮箱:jhc@sjtu.edu.cn 电话:021-54740299
邮编:200240