Loop Calculus for Satisfiability

Lukas Kroc; Michael Chertkov

Loop Calculus for Satisfiability

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Proceedings of the 23rd AAAI Conference on Artificial Intelligence, AAAI 2008
Publisher	AAAI press
Pages	1810-1811
Number of pages	2
ISBN (Electronic)	9781577353683
State	Published - 2008
Externally published	Yes
Event	23rd AAAI Conference on Artificial Intelligence, AAAI 2008 - Chicago, United States Duration: Jul 13 2008 → Jul 17 2008

Publication series

Name	Proceedings of the 23rd AAAI Conference on Artificial Intelligence, AAAI 2008

Conference

Conference	23rd AAAI Conference on Artificial Intelligence, AAAI 2008
Country/Territory	United States
City	Chicago
Period	7/13/08 → 7/17/08

ASJC Scopus subject areas

Artificial Intelligence

Cite this

@inproceedings{2b89b410282b4d1cae4aac6abed5202d,

title = "Loop Calculus for Satisfiability",

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

author = "Lukas Kroc and Michael Chertkov",

note = "Publisher Copyright: Copyright {\textcopyright} 2008, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.; 23rd AAAI Conference on Artificial Intelligence, AAAI 2008 ; Conference date: 13-07-2008 Through 17-07-2008",

year = "2008",

language = "English (US)",

series = "Proceedings of the 23rd AAAI Conference on Artificial Intelligence, AAAI 2008",

publisher = "AAAI press",

pages = "1810--1811",

booktitle = "Proceedings of the 23rd AAAI Conference on Artificial Intelligence, AAAI 2008",

}

TY - GEN

T1 - Loop Calculus for Satisfiability

AU - Kroc, Lukas

AU - Chertkov, Michael

PY - 2008

Y1 - 2008

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

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

UR - http://www.scopus.com/inward/record.url?scp=85167417122&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85167417122&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85167417122

T3 - Proceedings of the 23rd AAAI Conference on Artificial Intelligence, AAAI 2008

SP - 1810

EP - 1811

BT - Proceedings of the 23rd AAAI Conference on Artificial Intelligence, AAAI 2008

PB - AAAI press

T2 - 23rd AAAI Conference on Artificial Intelligence, AAAI 2008

Y2 - 13 July 2008 through 17 July 2008

ER -

Loop Calculus for Satisfiability

Abstract

Publication series

Conference

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this