Markov Chain for k-SAT Glauber Dynamics (X]VX2VX3)A(VXV x5)A (x4 Vx5VX6) Start from an arbitrary satisfyingx[T,F)V At each step: ·pick i∈V uniformly at random resamplex~以(·|x) A:uniform distribution over all SAT solutionsx[T,F]V .(marginal distribution ofcond.on current values of all other variablesMarkov Chain for k-SAT Start from an arbitrary satisfying At each step: • pick uniformly at random • resample x ∈ {𝚃, 𝙵}V i ∈ V xi ∼ μi ( ⋅ ∣ xV∖{i}) !" !# !$ !% !& !' !( (x1 ∨ ¬x2 ∨ x3) ∧ (x2 ∨ x7 ∨ x5) ∧ (x4 ∨ ¬x5 ∨ x6) T F • : uniform distribution over all SAT solutions • : marginal distribution of cond. on current values of all other variables μ x ∈ {𝚃, 𝙵}V μi ( ⋅ ∣ xV∖{i}) xi Glauber Dynamics