# Performance of the Survey Propagation-guided decimation algorithm for the random NAE-K-SAT problem

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

## Key facts

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

## 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)

We show that the Survey Propagation-guided decimation algorithm fails to find satisfying assignments on random instances of the "Not-All-Equal-K-SAT" problem if the number of message passing iterations is bounded by a constant independent of the size of the instance and the clause-to-variable ratio is above (1+oK(1))2K-1over Klog2 K for sufficiently large K. Our analysis in fact applies to a broad class of algorithms described as "sequential local algorithms". Such algorithms iteratively set variables based on some local information and then recurse on the reduced instance. Survey Propagation-guided as well as Belief Propagation-guided decimation algorithms - two widely studied message passing based algorithms, fall under this category of algorithms provided the number of message passing iterations is bounded by a constant. Another well-known algorithm falling into this category is the Unit Clause algorithm. Our work constitutes the first rigorous analysis of the performance of the SP-guided decimation algorithm. The approach underlying our paper is based on an intricate geometry of the solution space of random NAE-K-SAT problem. We show that above the (1+oK(1))2K-1over Klog2 K threshold, the overlap structure of m-tuples of satisfying assignments exhibit a certain clustering behavior expressed in the form of constraints on distances between the m assignments, for appropriately chosen m. We further show that if a sequential local algorithm succeeds in finding a satisfying assignment with probability bounded away from zero, then one can construct an m-tuple of solutions violating these constraints, thus leading to a contradiction. Along with (citation), this result is the first work which directly links the clustering property of random constraint satisfaction problems to the computational hardness of finding satisfying assignments.