General Questions for CSP Instances Decision:Can we efficiently determine if the instance has a solution? NP-hard for general 3-CNF formula ·Lovasz local lemma Search:If the CSP instance is satisfiable,can we find a solution efficiently? Constructive Lovasz local lemma Sampling:If we can efficiently find a solution,can we efficiently sample a uniform random solution from the whole solution space? Sampling Lovasz local lemma Our focus General Questions for CSP Instances • Decision: Can we efficiently determine if the instance has a solution? • NP-hard for general 3-CNF formula • Lovász local lemma • Search: If the CSP instance is satisfiable, can we find a solution efficiently? • Constructive Lovász local lemma • Sampling: If we can efficiently find a solution, can we efficiently sample a uniform random solution from the whole solution space? • Sampling Lovász local lemma Our focus