# Analysing Survey Propagation Guided Decimation on Random Formulas

arXiv: https://arxiv.org/abs/1602.08519 · HTML: https://mlsanity.com/paper/1602.08519/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Feb 2016.

## Built on by (most cited first, 1 of 1)

- [The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials](https://mlsanity.com/paper/2106.02129/) (2021)

## Abstract (arXiv)

Let varPhi be a uniformly distributed random k-SAT formula with n variables and m clauses. For clauses/variables ratio m/n ≤ rk-SAT ~ 2kln2 the formula varPhi is satisfiable with high probability. However, no efficient algorithm is known to provably find a satisfying assignment beyond m/n ~ 2k ln(k)/k with a non-vanishing probability. Non-rigorous statistical mechanics work on k-CNF led to the development of a new efficient "message passing algorithm" called Survey Propagation Guided Decimation [M'ezard et al., Science 2002]. Experiments conducted for k=3,4,5 suggest that the algorithm finds satisfying assignments close to rk-SAT. However, in the present paper we prove that the basic version of Survey Propagation Guided Decimation fails to solve random k-SAT formulas efficiently already for m/n=2k(1+varepsilonk)ln(k)/k with limk→∞varepsilonk= 0 almost a factor k below rk-SAT.