Perfect Sampling for(Atomic) Lovasz Local Lemma Kewen Wu (UC Berkeley) Joint with Kun He(ICT,CAS)and Xiaoming Sun(ICT,CAS)
Perfect Sampling for (Atomic) Lovász Local Lemma Kewen Wu (UC Berkeley) Joint with Kun He (ICT, CAS) and Xiaoming Sun (ICT, CAS)
Constraint Satisfaction Problem(CSP) Variable set V:Each v E V takes values in domain ·Constraint set C:Each c∈C is a constraint on vbl(c)∈V c:,→{True,False} vEvbl(c) Solution set Each o Eve such that all constraints are satisfied Atomic condition:Each constraint has exactly one falsifying assignment Examples: .CNF formula:=(x1 Vx2 Vx3)A (x2 Vx7)A (x3 Vx4) Hypergraph coloring:color vertices of a hypergraph without monochromatic hyperedge
Constraint Satisfaction Problem (CSP) • Variable set 𝑉: Each 𝑣 ∈ 𝑉 takes values in domain Ω𝑣 • Constraint set 𝐶: Each 𝑐 ∈ 𝐶 is a constraint on vbl(𝑐) ⊆ 𝑉 𝑐: ෑ 𝑣∈vbl(𝑐) Ω𝑣 → {𝐓𝐫𝐮𝐞,𝐅𝐚𝐥𝐬𝐞} • Solution set Σ: Each 𝜎 ∈ Σ ⊆ ς𝑣∈𝑉 Ω𝑣 such that all constraints are satisfied • Atomic condition: Each constraint has exactly one falsifying assignment Examples: • CNF formula: Φ = 𝑥1 ∨ ¬𝑥2 ∨ 𝑥3 ∧ 𝑥2 ∨ 𝑥7 ∧ ¬𝑥3 ∨ ¬𝑥4 • Hypergraph coloring: color vertices of a hypergraph without monochromatic hyperedge
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
Lovasz Local Lemma [Erdos and Lovasz'751 ·CSP instanceΦ=(W,C)with solution set∑ Each variable v is uniform in .Individual falsifying probability:p()=Prc is False] ·Degree:△（Φ）=max#{c'∈C I vbl(c)nvbl(c)≠0} ·Ife·p(Φ)·△（Φ）≤1，then≠0 Example: ·Φ=(x1Vx2Vx3)A(x2Vx7)A(x3Vx4) ·Then p(Φ)=1/4and△（Φ）=3
Lovász Local Lemma [Erdős and Lovász’75] • CSP instance Φ = 𝑉, 𝐶 with solution set Σ • Each variable 𝑣 is uniform in Ω𝑣 • Individual falsifying probability: 𝑝 Φ = max 𝑐∈𝐶 Pr[𝑐 is 𝐅𝐚𝐥𝐬𝐞] • Degree: Δ Φ = max 𝑐∈𝐶 # 𝑐 ′ ∈ 𝐶 vbl 𝑐 ∩ vbl 𝑐 ′ ≠ ∅ • If 𝑒 ⋅ 𝑝 Φ ⋅ Δ Φ ≤ 1, then Σ ≠ ∅ Example: • Φ = 𝑥1 ∨ ¬𝑥2 ∨ 𝑥3 ∧ 𝑥2 ∨ 𝑥7 ∧ ¬𝑥3 ∨ ¬𝑥4 • Then 𝑝 Φ = 1/4 and Δ Φ = 3
Examples ·k-CNF formula .(x1 V-x2 VX3)A (x2 Vx7V x8)A (x3 Vx4 Vx5) Each clause has exactly k literals Each variable appears in at most d clauses Satisfiableif ·Then p(Φ)=2-kand△（Φ）≤dk d s 2k ·Hypergraph coloring Each hyperedge has k vertices Each hyperedge intersects at most A other hyperedges Properly colorable if The color of each vertex chooses from q colors △sqk ·Then p(Φ)=ql-kand△（Φ）=△+1
Examples • 𝑘-CNF formula • 𝑥1 ∨ ¬𝑥2 ∨ 𝑥3 ∧ 𝑥2 ∨ 𝑥7 ∨ 𝑥8 ∧ ¬𝑥3 ∨ ¬𝑥4 ∨ 𝑥5 • Each clause has exactly 𝑘 literals • Each variable appears in at most 𝑑 clauses • Then 𝑝 Φ = 2 −𝑘 and Δ Φ ≤ 𝑑𝑘 • Hypergraph coloring • Each hyperedge has 𝑘 vertices • Each hyperedge intersects at most Δ other hyperedges • The color of each vertex chooses from 𝑞 colors • Then 𝑝 Φ = 𝑞 1−𝑘 and Δ Φ = Δ + 1 Satisfiable if 𝑑 ≲ 2 𝑘 Properly colorable if Δ ≲ 𝑞 𝑘