Analysing survey propagation guided decimationon random formulas

DOI10.4230/LIPICS.ICALP.2016.65MaRDI QIDQ4598204zbMATH OpenFDO

Authors Samuel Hetterich

Publication date 19 December 2017

Full work available at URL https://arxiv.org/abs/1602.08519

zbMATH Keywords

graph theorymessage-passing algorithmrandom \(k\)-SATsurvey-propagation-guided decimation

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Abstract: Let $varPhi$ be a uniformly distributed random $k$-SAT formula with $n$ variables and $m$ clauses. For clauses/variables ratio $m/nleq{r}_{kext-SAT}sim{2}^{k}ln2$ the formula $varPhi$ is satisfiable with high probability. However, no efficient algorithm is known to provably find a satisfying assignment beyond $m/nsim2kln(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 emph{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 $r_{kext-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=2^k(1+varepsilo{n}_k)ln(k)/k$ with $li{m}_{koinfty}varepsilo{n}_k=0$ almost a factor $k$ below $r_{kext-SAT}$.

Recommendations

• Belief propagation guided decimation fails on random formulas
• On belief propagation guided decimation for random k-SAT
• Survey propagation: An algorithm for satisfiability
• The decimation process in random \(k\)-SAT
• The decimation process in random k-SAT

Cited in

(18)

• Belief propagation on the random \(k\)-SAT model
• A new look at survey propagation and its generalizations
• Performance of sequential local algorithms for the random NAE-K-SAT problem
• The decimation process in random k-SAT
• Survey propagation as local equilibrium equations
• Belief propagation guided decimation fails on random formulas
• A new look at survey propagation and its generalizations
• The decimation process in random \(k\)-SAT
• Biased landscapes for random constraint satisfaction problems
• Counting solutions to random CNF formulas
• Walksat Stalls Well Below Satisfiability
• On belief propagation guided decimation for random k-SAT
• Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion
• The landscape of the planted clique problem: dense subgraphs and the overlap gap property
• Searching for (sharp) thresholds in random structures: where are we now?
• Counting solutions to random CNF formulas
• Sharp phase transitions for the overlap gap property
• Belief propagation guided decimation on random k-XORSAT

This page was built for publication: Analysing survey propagation guided decimationon random formulas

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4598204)