A Sampling Lovász Local Lemma for Large Domain Sizes
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909160610725888 |
|---|---|
| author | Wang, Chunyang Yin, Yitong |
| author_facet | Wang, Chunyang Yin, Yitong |
| contents | 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^2\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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_14872 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Sampling Lovász Local Lemma for Large Domain Sizes Wang, Chunyang Yin, Yitong Data Structures and Algorithms Probability 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^2\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. |
| title | A Sampling Lovász Local Lemma for Large Domain Sizes |
| topic | Data Structures and Algorithms Probability |
| url | https://arxiv.org/abs/2307.14872 |