Fetching the paper…
Reading the bibliography…
Message passing algorithms have proved surprisingly successful in solving hard constraint satisfaction problems on sparse random graphs.
J. Pearl, “Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference”, San Francisco, CA: Morgan Kaufmann, 1988
1988
Earlier work this paper cites.
A. Frieze and S. Suen, “Analysis of Two Simple Heuristics on a Random Instance of k-SAT”, Journal of Algorithms 20
1996
Earlier work this paper cites.
D. Achlioptas and G. B. Sorkin, Proc. of the Annual Symposium on the Foundations of Computer Science
2000
Earlier work this paper cites.
S. Janson, T. Luczak and A. Ruciński”, Random graphs
2000
Earlier work this paper cites.
G. Biroli, R. Monasson and M. Weigt, “A variational description of the ground state structure in random satisfiability problems”, Eur. Phys. J. B 14
2000
Earlier work this paper cites.
N. Creignou, S. Khanna and M. Sudan, Complexity classifications of boolean constraint satisfaction problems
2001
Earlier work this paper cites.
F. R. Kschischang, B. J. Frey and H-A. Loeliger, “Factor graphs and the sum-product algorithm” (2001), IEEE Trans. Inform. Theory
2001
Earlier work this paper cites.
J. Franco, “Results related to threshold phenomena research in satisfiability: lower bounds”, Theoret. Comput. Sci. 265
2001
Earlier work this paper cites.
M. Mézard, G. Parisi, and R. Zecchina, “Analytic and Algorithmic Solution of Random Satisfiability Problems”, Science 297 (2002), 812-815
2002
Earlier work this paper cites.
M. Mézard and R. Zecchina, “The random K K -satisfiability problem: from an analytic solution to an efficient algorithm”, Phys. Rev. E 66 (2002), 056126
2002
Earlier work this paper cites.
S. Tatikonda and M. Jordan, “Loopy Belief Propagation and Gibbs Measures”, Proc. Uncertainty in Artificial Intell
2002
Cited alongside, same era.
D. Aldous and J.M. Steele, “The objective method”, in Probability on Discrete Structures, H. Kesten ed., 1, Springer (2003)
2003
Cited alongside, same era.
D. Achlioptas and Y. Peres, “The threshold for random k k -SAT is 2 k log 2 − O ( k ) 2k\log 2-O(k) ”, Journal of the AMS, 17 (2004), 947-973
2004
Cited alongside, same era.
E. Aurell, U. Gordon and S. Kirkpatrick, Proc. of Neural Information Processing Symposium
2004
Cited alongside, same era.
C. Measson, A. Montanari, T. Richardson and R. Urbanke, “Life Above Threshold: From List Decoding to Area Theorem and MSE,” IEEE Inform. Theory Workshop, San Antonio, October 2004
2004
Cited alongside, same era.
S. Mertens, M. Mézard and R. Zecchina, “Threshold values of random K-SAT from the cavity method”, Random Struct. Alg. 28
2006
Later among the works it cites.
D. Gamarnik and A. Bandyopadhyay, Proc. of the Symposium on Discrete Algorithms
2006
Later among the works it cites.
U. Feige, E. Mossel and D. Vilenchik, “Complete convergence of message passing algorithms for some satisfiability problems” Proc. RANDOM
2006
Later among the works it cites.
F. Krzakala, A. Montanari, F. Ricci-Tersenghi, G. Semerjian and L. Zdeborova, “Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems,” Proc. Natl. Acad. Sci. 104 (2007) 10318-10323
2007
Closest in time.
A. Montanari and D. Shah, “Counting good truth assignments of random k-SAT formulae,” Proc. of the Symposium on Discrete Algorithms
2007
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
E. Maneva and M. Wainwright, “Lossy source encoding via message-passing and decimation over generalized codewords of LDGM codes,” IEEE Inform. Theory Symposium, Adelaide, September 2004
2004
Cited alongside, same era.
E. N. Maneva, E. Mossel and M. J. Wainwright, Proc. of the Symposium on Discrete Algorithms
2005
Cited alongside, same era.
S. Ciliberti, M. Mézard and R. Zecchina, “Lossy data compression with random gates,” Phys. Rev. Lett. 95
2005
Cited alongside, same era.
A. Braunstein, M. Mézard and R. Zecchina, “Survey propagation: an algorithm for satisfiability”, Random Structures and Algorithms 27
2005
Cited alongside, same era.
B. Selman, H. Levesque and D. Mitchell, “A New Method for Solving Hard Satisfiability Problems”, 10th Natl Conf. on Artif. Intell., San Jose, CA, 440-446
Cited in the paper.
S. J. Pumphrey, “Solving the Satisfiability Problem Using Message Passing Techniques,” Cambridge Physics Project Report
Cited in the paper.
T. Richardson and R. Urbanke, Modern Coding Theory
Cited in the paper.
A. Coja-Oghlan, M. Krivelevich and D. Vilenchik, “Why almost all k k -CNF formulas are easy”, Proceedings of the 13th International Conference on Analysis of Algorithms, to appear, (2007)
2007
Closest in time.
F. Altarelli, R. Monasson and F. Zamponi, “Can rare SAT formulae be easily recognized? On the efficiency of message-passing algorithms for K-SAT at large clause-to-variable ratios”, J. Phys. A: Math. Theor. 40
2007
Closest in time.
A. Gerschenfeld and A. Montanari, Proc. of the Annual Symposium on the Foundations of Computer Science
2007
Closest in time.
M. Luby, M. Mitzenmacher and A. Shokrollahi, “Analysis of Random Processes via And-Or Tree Evaluation” Proc. of the Symposium on Discrete Algorithms
2008
Closest in time.