Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Comparing Beliefs, Surveys and Random Walks
KTH, School of Engineering Sciences (SCI), Physics. Swedish Institute of Computer Science, Sweden .
2005 (English)In: Advances in Neural Information Processing Systems 17: proceedings of the 2004 conference, Morgan Kaufmann Publishers, 2005Conference paper, Published paper (Refereed)
Abstract [en]

Survey propagation is a powerful technique from statistical physics that has been applied to solve the 3-SAT problem both in principle and in practice. We give, using only probability arguments, a common derivation of survey propagation, belief propagation and several interesting hybrid methods. We then present numerical experiments which use WSAT (a widely used random-walk based SAT solver) to quantify the complexity of the 3-SAT formulae as a function of their parameters, both as randomly generated and after simplification, guided by survey propagation. Some properties of WSAT which have not previously been reported make it an ideal tool for this purpose - its mean cost is proportional to the number of variables in the formula (at a fixed ratio of clauses to variables) in the easy-SAT regime and slightly beyond, and its behavior in the hard- SAT regime appears to refiect the underlying structure of the solution space that has been predicted by replica symmetry-breaking arguments. An analysis of the tradeoffs between the various methods of search for satisfying assignments shows WSAT to be far more powerful than has been appreciated, and suggests some interesting new directions for practical algorithm development.

Place, publisher, year, edition, pages
Morgan Kaufmann Publishers, 2005.
Series
Advances in Neural Information Processing Systems, ISSN 1049-5258 ; 17
Keyword [en]
3-SAT problems, Algorithm development, Belief propagation, Numerical experiments, Satisfying assignments, Statistical physics, Survey propagation, Symmetry-breaking
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-57734Scopus ID: 2-s2.0-84898998239ISBN: 978-026219534-8 ISBN: 0262195348 (print)OAI: oai:DiVA.org:kth-57734DiVA: diva2:472572
Conference
18th Annual Conference on Neural Information Processing Systems, NIPS 2004, Vancouver, BC, Canada, 13 December 2004 through 16 December 2004
Note

QC 20120117

Available from: 2012-01-04 Created: 2012-01-04 Last updated: 2015-04-10Bibliographically approved

Open Access in DiVA

No full text

Scopus

Search in DiVA

By author/editor
Aurell, Erik
By organisation
Physics
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 35 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf