A Sampling Lovász Local Lemma for Large Domain Sizes

2023/07/27 by Chunyang Wang, Wang, Chunyang, Yitong Yin +1 · 1 citation
Computer Science · Mathematics · #Machine Learning and Algorithms #Markov Chains and Monte Carlo Methods #Complexity and Algorithms in Graphs

paper · pdf · doi:10.48550/arxiv.2307.14872

Abstract

We present polynomial-time algorithms for approximate counting and sampling solutions to constraint satisfaction problems (CSPs) with atomic constraints within the local lemma regime: pD^2+o_q(1)\lesssim 1. When the domain size q of each variable becomes sufficiently large, this almost matches the known lower bound pD²\gtrsim 1 for approximate counting and sampling solutions to atomic CSPs [Bezáková et al, SICOMP '19; Galanis, Guo, Wang, TOCT '22], thus establishing an almost tight sampling Lovász local lemma for large domain sizes.

Cited by

• Learning CNF formulas from uniform random solutions in the local lemma regime

Related

• Sampling Lovász Local Lemma For General Constraint Satisfaction Solutions In Near-Linear Time
• Deterministic counting Lovász local lemma beyond linear programming
• Perfect Sampling for (Atomic) Lovász Local Lemma
• Sampling Constraint Satisfaction Solutions in the Local Lemma Regime
• Towards the sampling Lovász Local Lemma