The random $k$-SAT Gibbs uniqueness threshold revisited
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911272614756352 |
|---|---|
| author | Chatterjee, Arnab Coja-Oghlan, Amin Greenhill, Catherine Pfenninger, Vincent Rolvien, Maurice Zakharov, Pavel Zampetakis, Kostas |
| author_facet | Chatterjee, Arnab Coja-Oghlan, Amin Greenhill, Catherine Pfenninger, Vincent Rolvien, Maurice Zakharov, Pavel Zampetakis, Kostas |
| contents | We prove that for any $k\geq3$ for clause/variable ratios up to the Gibbs uniqueness threshold of the corresponding Galton-Watson tree, the number of satisfying assignments of random $k$-SAT formulas is given by the `replica symmetric solution' predicted by physics methods [Monasson, Zecchina: Phys. Rev. Lett. (1996)]. Furthermore, while the Gibbs uniqueness threshold is still not known precisely for any $k\geq3$, we derive new lower bounds on this threshold that improve over prior work [Montanari and Shah: SODA (2007)].The improvement is significant particularly for small $k$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_01359 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The random $k$-SAT Gibbs uniqueness threshold revisited Chatterjee, Arnab Coja-Oghlan, Amin Greenhill, Catherine Pfenninger, Vincent Rolvien, Maurice Zakharov, Pavel Zampetakis, Kostas Discrete Mathematics Combinatorics Probability 68Q87, 60C05, 68R07 We prove that for any $k\geq3$ for clause/variable ratios up to the Gibbs uniqueness threshold of the corresponding Galton-Watson tree, the number of satisfying assignments of random $k$-SAT formulas is given by the `replica symmetric solution' predicted by physics methods [Monasson, Zecchina: Phys. Rev. Lett. (1996)]. Furthermore, while the Gibbs uniqueness threshold is still not known precisely for any $k\geq3$, we derive new lower bounds on this threshold that improve over prior work [Montanari and Shah: SODA (2007)].The improvement is significant particularly for small $k$. |
| title | The random $k$-SAT Gibbs uniqueness threshold revisited |
| topic | Discrete Mathematics Combinatorics Probability 68Q87, 60C05, 68R07 |
| url | https://arxiv.org/abs/2506.01359 |