Name
Abstract | ||
|---|---|---|
Experimental results show that certain message passing algorithms, namely, survey propa- gation, are very efiective in flnding satisfying assignments in random satisflable 3CNF formulas. In this paper we make a modest step towards providing rigorous analysis that proves the ef- fectiveness of message passing algorithms for random 3SAT. We analyze the performance of Warning Propagation, a popular message passing algorithm that is simpler than survey propa- gation. We show that for 3CNF formulas generated under the planted assignment distribution, running warning propagation in the standard way (run message passing until convergence, sim- plify the formula according to the resulting assignment, and satisfy the remaining subformula, if necessary, using a simple \ofi the shelf" heuristic) works when the clause-to-variable ratio is a su-ciently large constant. We are not aware of previous rigorous analysis of message passing algorithms for satisflability instances, though such analysis was performed for decoding of Low Density Parity Check (LDPC) Codes. We discuss some of the difierences between results for the LDPC setting and our results. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/11830924_32 | Theory of Computing |
Keywords | Field | DocType |
satisfiability problem,assignment distribution,rigorous analysis,survey propagation,previous rigorous analysis,complete convergence,low density parity check,random satisfiable,ldpc setting,certain message,popular message,warning propagation,ldpc code,variable ratio,message passing,satisfiability | Factor graph,Parity bit,Approximation algorithm,Random graph,Low-density parity-check code,Computer science,Satisfiability,Boolean satisfiability problem,Algorithm,Theoretical computer science,Message passing,Distributed computing | Journal |
Volume | Issue | ISSN |
9 | 1 | 0302-9743 |
ISBN | Citations | PageRank |
3-540-38044-2 | 22 | 1.02 |
References | Authors | |
27 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Uriel Feige | 1 | 5647 | 560.87 |
| Elchanan Mossel | 2 | 1725 | 145.16 |
| Dan Vilenchik | 3 | 143 | 13.36 |