Loop Calculus for Satisfiability

Lukas Kroc, Michael Chertkov

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 (US)
Title of host publicationProceedings of the 23rd AAAI Conference on Artificial Intelligence, AAAI 2008
PublisherAAAI press
Pages1810-1811
Number of pages2
ISBN (Electronic)9781577353683
StatePublished - 2008
Externally publishedYes
Event23rd AAAI Conference on Artificial Intelligence, AAAI 2008 - Chicago, United States
Duration: Jul 13 2008Jul 17 2008

Publication series

NameProceedings of the 23rd AAAI Conference on Artificial Intelligence, AAAI 2008

Conference

Conference23rd AAAI Conference on Artificial Intelligence, AAAI 2008
Country/TerritoryUnited States
CityChicago
Period7/13/087/17/08

ASJC Scopus subject areas

  • Artificial Intelligence

Cite this