Hacker News Reader

Parent Full thread

AxEy

I'm afraid I was not familiar, although I'm looking at a few related papers on the arxiv now.

What brought that approach to mind?

View on HN

Survey Propagation is one of the best algorithms for solving very hard SAT instances.

Here's a good review paper that captures it.

http://www.cs.cornell.edu/~sabhar/publications/surveyPropUAI...

Thanks

Survey propagation works primarily with random SAT instances, but isn't competitive with SAT instances that arise in industrial verification, where CDCL shines. Some gossip: survey propagation was proposed by Mezard, Parisi, and Zecchina [1], and G. Parisi won the physics Nobel price in 2021 [2].

[1] M. Mezard, G. Parisi, R. Zecchina, Analytic and Algorithmic Solution of Random Satisfiability Problems. https://aiichironakano.github.io/cs653/Mezard-RSAT-Science02...

[2] https://en.wikipedia.org/wiki/Giorgio_Parisi

Reply on news.ycombinator.com