ML Anthology

Loop Calculus for Satisfiability

Lukas Kroc, Michael Chertkov
AAAI 2008 pp. 1810-1811
/aaai/2008/kroc2008aaai-loop/

Abstract

Loop Calculus, introduced by Chertkov and Chernyak, is a new technique to incrementally improve approximations computed by Loopy Belief Propagation (LBP), with the ability to eventually make them exact. In this extended abstract, we give a brief overview of this technique, and show its relevance to the AI community. We consider the problem of Boolean Satisfiability (SAT) and use LBP with Loop Calculus corrections to perform probabilistic inference about the problem. In this preliminary work, we focus on identifying the main issues encountered when applying Loop Calculus, and include initial empirical results in the SAT domain.

PDF AAAI Semantic Scholar

Cite

Text

Kroc and Chertkov. "Loop Calculus for Satisfiability." AAAI Conference on Artificial Intelligence, 2008.

Markdown

[Kroc and Chertkov. "Loop Calculus for Satisfiability." AAAI Conference on Artificial Intelligence, 2008.](https://mlanthology.org/aaai/2008/kroc2008aaai-loop/)

BibTeX

@inproceedings{kroc2008aaai-loop,
  title     = {{Loop Calculus for Satisfiability}},
  author    = {Kroc, Lukas and Chertkov, Michael},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2008},
  pages     = {1810-1811},
  url       = {https://mlanthology.org/aaai/2008/kroc2008aaai-loop/}
}