Loop calculus for satisfiability

Lukas Kroc, Michael Chertkov

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

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.,

Original languageEnglish
Title of host publicationAAAI-08/IAAI-08 Proceedings - 23rd AAAI Conference on Artificial Intelligence and the 20th Innovative Applications of Artificial Intelligence Conference
Pages1810-1811
Number of pages2
Publication statusPublished - 2008
Externally publishedYes
Event23rd AAAI Conference on Artificial Intelligence and the 20th Innovative Applications of Artificial Intelligence Conference, AAAI-08/IAAI-08 - Chicago, IL, United States
Duration: 13 Jul 200817 Jul 2008

Publication series

NameProceedings of the National Conference on Artificial Intelligence
Volume3

Conference

Conference23rd AAAI Conference on Artificial Intelligence and the 20th Innovative Applications of Artificial Intelligence Conference, AAAI-08/IAAI-08
Country/TerritoryUnited States
CityChicago, IL
Period13/07/0817/07/08

Cite this