Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems.
Uriel FeigeElchanan MosselDan VilenchikPublished in: APPROX-RANDOM (2006)
Keyphrases
- message passing
- satisfiability problem
- sum product algorithm
- matrix multiplication
- stochastic local search
- belief propagation
- inference in graphical models
- np complete
- optimization problems
- temporal logic
- distributed systems
- shared memory
- orders of magnitude
- graphical models
- approximate inference
- loopy belief propagation
- factor graphs
- pspace complete
- dynamic programming
- search algorithm
- bayesian networks