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?