南京大学：《计算理论之美》课程教学资源（课件讲稿）Perfect Sampling for（Atomic）Lovász Local Lemma

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 Δ ≲ 𝑞 𝑘

Constructive Lovasz Local Lemma [Bec'91,Alo'91,MR'98,CS'00,Mos'09,MT'10,KM'11,HSS'11,HS'17,HS'19] 。CSP instanceΦ=(V,C)with solution set∑ Each variable v is uniform in Individual falsifying probability:p()=max Pr[c is False] ·Degree:△（Φ）=max#{c'∈C|vbl(c)nvbl(c)≠o} ·fe·p(Φ)·△（Φ）≤l,then we can find some o∈ in probabilistic linear time or in deterministic polynomial time

Constructive Lovász Local Lemma [Bec’91, Alo’91, MR’98, CS’00, Mos’09, MT’10, KM’11, HSS’11, HS’17, HS’19] • CSP instance Φ = 𝑉,𝐶 with solution set Σ • Each variable 𝑣 is uniform in Ω𝑣 • Individual falsifying probability: 𝑝 Φ = max 𝑐∈𝐶 Pr[𝑐 is 𝐅𝐚𝐥𝐬𝐞] • Degree: Δ Φ = max 𝑐∈𝐶 # 𝑐 ′ ∈ 𝐶 vbl 𝑐 ∩ vbl 𝑐 ′ ≠ ∅ • If 𝑒 ⋅ 𝑝 Φ ⋅ Δ Φ ≤ 1, then we can find some 𝜎 ∈ Σ • in probabilistic linear time • or in deterministic polynomial time

Sampling Lovasz Local Lemma [Moi'19,GLLZ'19,FGYZ'20,FHY'20,JPV'20,JPV'21] ·Given local lemma type conditions,,efficiently sample a uniform o∈∑ ·k-CNF formula ·Constructive::d≤2k Perfect uniform ·Approx.uniform:d≤20.175k [UPV'21] d≤20.175k ·Sampling hardness:d≥2k/2 [BGG+'19] Simple algorithm ·Hypergraph coloring Simple analysis Perfect uniform ·Constructive:△sqgk ·Approx.uniform:△sgk/3 △≤qk3 [UPV'21] Expected running 。General atomic CSPs time:0(n logn) ·Constructive:epA≤l Perfect uniform ·Approx.uniform:p0.142A≤1 [UPV'20] p0.175As1

Sampling Lovász Local Lemma [Moi’19, GLLZ’19, FGYZ’20, FHY’20, JPV’20, JPV’21] • Given local lemma type conditions, efficiently sample a uniform 𝜎 ∈ Σ • 𝑘-CNF formula • Constructive: 𝑑 ≲ 2 𝑘 • Approx. uniform: 𝑑 ≲ 2 0.175𝑘 [JPV’21] • Sampling hardness: 𝑑 ≳ 2 𝑘/2 [BGG+’19] • Hypergraph coloring • Constructive: Δ ≲ 𝑞 𝑘 • Approx. uniform: Δ ≲ 𝑞 𝑘/3 [JPV’21] • General atomic CSPs • Constructive: 𝑒𝑝Δ ≤ 1 • Approx. uniform: 𝑝 0.142Δ ≲ 1 [JPV’20] Perfect uniform 𝑑 ≲ 2 0.175𝑘 Perfect uniform Δ ≲ 𝑞 𝑘/3 Perfect uniform 𝑝 0.175Δ ≲ 1 Simple algorithm Simple analysis Expected running time: 𝑂(𝑛 log𝑛)

Our Results:Arbitrary Distribution ·CSP instanceΦ=(V,C)with solution set∑ Each variable v has distribution Du overo Individual falsifying probability:p=max Pr[c is False] D is uniform cEc →x=2andy>0.145 ·Degree::△=max#{c'∈C I vbl(c)nvbl(c')≠o} Already beats 0.142 from [JPV'20] Smoothness:K=max 2,maxmax Dv(q) VEV q.q'En Du(q') +ln(K+1)-V1n2(x+1)+61ln(k+1) ·lfpY·△≤1/x,then we can r= 9 ·sampleo∈∑under distributionΠDo ·in expected O(n log n) is a solution]

Our Results: Arbitrary Distribution • CSP instance Φ = 𝑉, 𝐶 with solution set Σ • Each variable 𝑣 has distribution 𝐷𝑣 over Ω𝑣 • Individual falsifying probability: 𝑝 = max 𝑐∈𝐶 Pr[𝑐 is 𝐅𝐚𝐥𝐬𝐞] • Degree: Δ = max 𝑐∈𝐶 # 𝑐 ′ ∈ 𝐶 vbl 𝑐 ∩ vbl 𝑐 ′ ≠ ∅ • Smoothness: 𝜅 = max 2, max 𝑣∈𝑉 max 𝑞,𝑞 ′∈Ω𝑣 𝐷𝑣 𝑞 𝐷𝑣 𝑞 ′ • If 𝑝 𝛾 ⋅ Δ ≲ 1/𝜅, then we can • sample 𝜎 ∈ Σ under distribution ς𝐷𝑣 • in expected 𝑂 𝑛 log 𝑛 𝛾 = 3 + ln(𝜅 + 1) − ln2(𝜅 + 1) + 6 ln 𝜅 + 1 9 Pr 𝜎∼ς𝐷𝑣 [⋅∣ 𝜎 is a solution] 𝐷𝑣 is uniform ⇒ 𝜅 = 2 and 𝛾 > 0.145 Already beats 0.142 from [JPV’20]

Our Results:Uniform Distribution ·CSP instanceΦ=(V,C)with solution set∑ Each variable v has uniform distribution over Individual falsifying probability:p max Pr[c is False] ·Degree:△=max#{c'∈C|vbl(c)nvbl(c)≠0} ·lfp0.175.△≤1，then we can Beats 0.142 from [JPV'20] Matches 0.175 for k-CNF formula from [JPV'21] ·sample uniform random o∈∑ ·in expected O(n log n) Indeed k-CNF case is our bottleneck If each is large enough,it can be improved to p2/3.△s1 Hypergraph coloring

Our Results: Uniform Distribution • CSP instance Φ = 𝑉,𝐶 with solution set Σ • Each variable 𝑣 has uniform distribution over Ω𝑣 • Individual falsifying probability: 𝑝 = max 𝑐∈𝐶 Pr[𝑐 is 𝐅𝐚𝐥𝐬𝐞] • Degree: Δ = max 𝑐∈𝐶 # 𝑐 ′ ∈ 𝐶 vbl 𝑐 ∩ vbl 𝑐 ′ ≠ ∅ • If 𝑝 0.175 ⋅ Δ ≲ 1, then we can • sample uniform random 𝜎 ∈ Σ • in expected 𝑂 𝑛 log 𝑛 Beats 0.142 from [JPV’20] Matches 0.175 for 𝑘-CNF formula from [JPV’21] Indeed 𝑘-CNF case is our bottleneck If each Ω𝑣 is large enough, it can be improved to 𝑝 1/3 ⋅ Δ ≲ 1 Hypergraph coloring

Perfect Sampling vs Approximate Sampling ·D1 is uniform over{1,2,…,n} .D2 is uniform over {1,2,...,n-vn} .The total variation distance between Dand D is=o(1) Fairness:all solutions are created equal! Indeed the case for [FGYZ'20,FHY'20,JPV'21] Some solutions are never outputted Solutions inherently hard to find?

Perfect Sampling vs Approximate Sampling • 𝐷1 is uniform over 1,2, … , 𝑛 • 𝐷2 is uniform over 1,2, … , 𝑛 − 𝑛 • The total variation distance between 𝐷1 and 𝐷2 is 𝑂 1 𝑛 = 𝑜 1 • Fairness: all solutions are created equal! • Indeed the case for [FGYZ’20, FHY’20, JPV’21] • Some solutions are never outputted • Solutions inherently hard to find?