Message-passing and local heuristics as decimation strategies for satisfiability.
Lukas KrocAshish SabharwalBart SelmanPublished in: SAC (2009)
Keyphrases
- message passing
- belief propagation
- distributed systems
- probabilistic inference
- factor graphs
- shared memory
- graphical models
- approximate inference
- sum product algorithm
- distributed shared memory
- sum product
- satisfiability problem
- inference in graphical models
- search algorithm
- matrix multiplication
- computational complexity
- pairwise
- phase transition
- junction tree
- graph cuts
- higher order
- search space
- preprocessing