Performance of the Survey Propagation-guided decimation algorithm for the random NAE-K-SAT problem

Richard M Karp, The probabilistic analysis of some combinatorial search algorithms , Algorithms and complexity: New directions and recent results 1

1976

Earlier work this paper cites.

Leonid A Levin, Average case complete problems , SIAM Journal on Computing 15

1986

Earlier work this paper cites.

Dimitris Achlioptas, Michael Krivelevich, Prasad Tetali, et al., Two-coloring random hypergraphs , Random Structures & Algorithms 20

2002

Earlier work this paper cites.

Marc Mézard, Giorgio Parisi, and Riccardo Zecchina, Analytic and algorithmic solution of random satisfiability problems , Science 297

2002

Earlier work this paper cites.

D. Aldous and J. M. Steele, The objective method: Probabilistic combinatorial optimization and local weak convergence , Discrete Combinatorial Probability, H. Kesten Ed., Springer-Verlag, 2003

2003

Earlier work this paper cites.

A. Braunstein, M. Mézard, and R. Zecchina, Survey propagation: An algorithm for satisfiability , Random Structures & Algorithms 27

2005

Earlier work this paper cites.

D. Gamarnik, T. Nowicki, and G. Swirscsz, Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method , Random Structures and Algorithms 28

2006

Earlier work this paper cites.

F. Krzakała, A. Montanari, F. Ricci-Tersenghi, G. Semerjian, and L. Zdeborová, Gibbs states and the set of solutions of random constraint satisfaction problems , Proceedings of the National Academy of Sciences 104

2007

Earlier work this paper cites.

Elitza Maneva, Elchanan Mossel, and Martin J Wainwright, A new look at survey propagation and its generalizations , Journal of the ACM (JACM) 54

2007

Cited alongside, same era.

A. Bandyopadhyay and D. Gamarnik, Counting without sampling. Asymptotics of the log-partition function for certain statistical physics models , Random Structures and Algorithms 33

2008

Cited alongside, same era.

Luca Dall’Asta, Abolfazl Ramezanpour, and Riccardo Zecchina, Entropy landscape and non-gibbs solutions in constraint satisfaction problems , Physical Review E 77

2008

Cited alongside, same era.

H.N. Nguyen and K. Onak, Constant-time approximation algorithms via local improvements , Foundations of Computer Science, 2008. FOCS’08. IEEE 49th Annual IEEE Symposium on, IEEE, 2008, pp. 327–336

2008

Cited alongside, same era.

M. Mezard and A. Montanari, Information, physics and computation , Oxford graduate texts, 2009

A. Coja-Oghlan, On belief propagation guided decimation for random k-SAT , Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2011, pp. 957–966

2011

Later among the works it cites.

A. Coja-Oghlan and C. Efthymiou, On independent sets in random graphs , Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2011, pp. 136–144

2011

Later among the works it cites.

Andrea Montanari, Ricardo Restrepo, and Prasad Tetali, Reconstruction and clustering in random constraint satisfaction problems , SIAM Journal on Discrete Mathematics 25

2011

Later among the works it cites.

A. Coja-Oglan and K. Panagiotou, Catching the k-NAESAT threshold , Proceedings of the 44th symposium on Theory of Computing, ACM, 2012, pp. 899–908

2012

Later among the works it cites.

Lukas Kroc, Ashish Sabharwal, and Bart Selman, Survey propagation revisited , arXiv preprint arXiv:1206.5273 (2012)