NDLI: A new look at survey propagation and its generalizations

Content Provider	ACM Digital Library
Author	Maneva, Elitza Mossel, Elchanan Wainwright, Martin J.
Copyright Year	2007
Abstract	This article provides a new conceptual perspective on survey propagation, which is an iterative algorithm recently introduced by the statistical physics community that is very effective in solving random $\textit{k}-SAT$ problems even with densities close to the satisfiability threshold. We first describe how any SAT formula can be associated with a novel family of Markov random fields (MRFs), parameterized by a real number ρ ∈ [0, 1]. We then show that applying belief propagation---a well-known “message-passing” technique for estimating marginal probabilities---to this family of MRFs recovers a known family of algorithms, ranging from pure survey propagation at one extreme (ρ = 1) to standard belief propagation on the uniform distribution over SAT assignments at the other extreme (ρ = 0). Configurations in these MRFs have a natural interpretation as partial satisfiability assignments, on which a partial order can be defined. We isolate $\textit{cores}$ as minimal elements in this partial ordering, which are also fixed points of survey propagation and the only assignments with positive probability in the MRF for ρ = 1. Our experimental results for $\textit{k}$ = 3 suggest that solutions of random formulas typically do not possess non-trivial cores. This makes it necessary to study the structure of the space of partial assignments for ρ < 1 and investigate the role of assignments that are very close to being cores. To that end, we investigate the associated lattice structure, and prove a weight-preserving identity that shows how any MRF with ρ > 0 can be viewed as a “smoothed” version of the uniform distribution over satisfying assignments (ρ = 0). Finally, we isolate properties of Gibbs sampling and message-passing algorithms that are typical for an ensemble of $\textit{k}-SAT$ problems.
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/1255443.1255445
Journal	Journal of the ACM (JACM)
Volume Number	54
Issue Number	4
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2007-07-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	k-SAT Gibbs sampling Markov random field Satisfiability problems Belief propagation Factor graph Message-passing Sum-product Survey propagation
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Control and Systems Engineering Artificial Intelligence Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A new look at survey propagation and its generalizations.

A new look at Survey Propagation and its generalizations (2007)

A new look at survey propagation and its generalizations (2004).

A new look at survey propagation and its generalizations (2005)

A new look at survey propagation and its generalizations (2005)

A new look at survey propagation and its generalizations (2005)

Analysing Survey Propagation Guided Decimationon Random Formulas

Consensus propagation

Message-passing and local heuristics as decimation strategies for satisfiability

A new look at survey propagation and its generalizations

Similar Documents

A new look at survey propagation and its generalizations.

A new look at Survey Propagation and its generalizations (2007)

A new look at survey propagation and its generalizations (2004).

A new look at survey propagation and its generalizations (2005)

A new look at survey propagation and its generalizations (2005)

A new look at survey propagation and its generalizations (2005)

Analysing Survey Propagation Guided Decimationon Random Formulas

Consensus propagation

Message-passing and local heuristics as decimation strategies for satisfiability

A new look at survey propagation and its generalizations