Abstract: The space of constraint satisfaction solutions is one of the most well-studied subjects in Computer Science.

Given a collection of constraints (or clauses) defined on a set of variables, each clause contains k Boolean variables and each variable appears in at most d clauses, a solution to the constraint satisfaction problem (CSP) is an assignment of variables such that all constraints are satisfied.

When k \gtrsim log d, Lovasz Local Lemma shows that there must exist a solution and algorithmic LLL, developed by Moser and Tardos, ensured that a solution can be constructed in polynomial time.

A more challenging problem raised then: how to sample a solution of CSP.

The disconnected solution space, via local updates of variables, even when the existence of solutions is guaranteed by the local lemma, is the major difficulty for efficiently sampling.

In this talk, we will review recent works that trying to bypass such connectivity barrier.