Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems
by Uriel Feige, Elchanan Mossel, and Dan Vilenchik
Theory of Computing, Volume 9(19), pp. 617-651, 2013
Bibliography with links to cited articles
[1] Dimitris Achlioptas and Amin Coja-Oghlan: Algorithmic barriers from phase transitions. In Proc. 49th FOCS, pp. 793–802. IEEE Comp. Soc. Press, 2008. [doi:10.1109/FOCS.2008.11]
[2] Dimitris Achlioptas, Amin Coja-Oghlan, and Federico Ricci-Tersenghi: On the solution-space geometry of random constraint satisfaction problems. Random Structures & Algorithms, 38(3):251–268, 2011. Preliminary version in STOC’06. [doi:10.1002/rsa.20323]
[3] Mikhail Alekhnovich and Eli Ben-Sasson: Linear upper bounds for random walk on small density random 3-CNFs. SIAM J. Comput., 36(5):1248–1263, 2007. Preliminary version in FOCS’03. [doi:10.1137/S0097539704440107]
[4] Noga Alon and Nabil Kahale: A spectral technique for coloring random 3-colorable graphs. SIAM J. Comput., 26(6):1733–1748, 1997. Prelimiary version in STOC’94. [doi:10.1137/S0097539794270248]
[5] Noga Alon, Michael Krivelevich, and Benny Sudakov: Finding a large hidden clique in a random graph. Random Structures & Algorithms, 13(3-4):457–466, 1998. Preliminary version in SODA’98. [doi:10.1002/(SICI)1098-2418(199810/12)13:3/4¡457::AID-RSA14¿3.0.CO;2-W]
[6] Noga Alon and Joel Spencer: The Probabilistic Method. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, 2nd edition, 2000.
[7] Alfredo Braunstein, Marc Mézard, and Riccardo Zecchina: Survey propagation: An algorithm for satisfiability. Random Structures & Algorithms, 27(2):201–226, 2005. [doi:10.1002/rsa.20057]
[8] Andrei Z. Broder, Alan M. Frieze, and Eli Upfal: On the satisfiability and maximum satisfiability of random 3-CNF formulas. In Proc. 4th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’93), pp. 322–330. ACM Press, 1993. [ACM:313559.313794]
[9] Hui Chen and Alan M. Frieze: Coloring bipartite hypergraphs. In Proc. 5th Ann. Conf. on Integer Programming and Combinatorial Optimization (IPCO ’96), pp. 345–358, London, UK, 1996. Springer. [doi:10.1007/3-540-61310-2_26]
[10] Amin Coja-Oghlan: A better algorithm for random k-SAT. SIAM J. Comput., 39(7):2823–2864, 2010. Preliminary version in ICALP’09. [doi:10.1137/09076516X]
[11] Amin Coja-Oghlan, Michael Krivelevich, and Dan Vilenchik: Why almost all k-CNF formulas are easy. In Proc. 13th Internat. Conf. on Analysis of Algorithms (AofA’07), pp. 89–102. DMTCS, 2007. DMTCS.
[12] Amin Coja-Oghlan and Angelica Y. Pachon-Pinzon: The decimation process in random k-SAT. SIAM J. Discrete Math., 26(4):1471–1509, 2012. Preliminary versions in ICALP’11 and SODA’11. [doi:10.1137/110842867]
[13] Stephen A. Cook: The complexity of theorem-proving procedures. In Proc. 3rd STOC, pp. 151–158. ACM Press, 1971. [doi:10.1145/800157.805047]
[14] James M. Crawford and Larry D. Auton: Experimental results on the crossover point in random 3-SAT. Artif. Intell., 81(1-2):31–57, 1996. Preliminary version in AAAI’93. [doi:10.1016/0004-3702(95)00046-1]
[15] Olivier Dubois, Yacine Boufkhad, and Jacques Mandler: Typical random 3-SAT formulae and the satisfiability threshold. In Proc. 11th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’00), pp. 126–127. ACM Press, 2000. [ACM:338243]
[16] Uriel Feige, Elchanan Mossel, and Dan Vilenchik: Complete convergence of message passing algorithms for some satisfiability problems. In Proc. 10th Internat. Workshop on Randomization and Computation (RANDOM’06), pp. 339–350. Springer, 2006. [doi:10.1007/11830924_32]
[17] Uriel Feige and Dan Vilenchik: A local search algorithm for 3SAT. Technical report, The Weizmann Institute of Science, 2004. Available at author’s home page.
[18] Abraham Flaxman: A spectral technique for random satisfiable 3CNF formulas. Random Structures & Algorithms, 32(4):519–534, 2008. Preliminary version in SODA’03. [doi:10.1002/rsa.20213]
[19] Ehud Friedgut: Sharp thresholds of graph properties, and the k-SAT problem. J. Amer. Math. Soc., 12(4):1017–1054, 1999. [doi:10.1090/S0894-0347-99-00305-7]
[20] Wassily Hoeffding: Probability inequalities for sums of bounded random variables. J. Amer. Stat. Assoc., 58(301):13–30, 1963. JSTOR.
[21] Alexis C. Kaporis, Lefteris M. Kirousis, and Efthimios G. Lalas: The probabilistic analysis of a greedy satisfiability algorithm. Random Structures & Algorithms, 28(4):444–480, 2006. Preliminary version in ESA’02. [doi:10.1002/rsa.20104]
[22] Elias Koutsoupias and Christos H. Papadimitriou: On the greedy algorithm for satisfiability. Inform. Process. Lett., 43(1):53–55, 1992. [doi:10.1016/0020-0190(92)90029-U]
[23] Michael Krivelevich and Dan Vilenchik: Solving random satisfiable 3CNF formulas in expected polynomial time. In Proc. 17th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’06), pp. 454–463. ACM Press, 2006. [doi:10.1145/1109557.1109608]
[24] Michael Luby, Michael Mitzenmacher, Amin Shokrollahi, and Daniel A. Spielman: Efficient erasure correcting codes. IEEE Trans. Inform. Theory, 47(2):569–584, 2001. [doi:10.1109/18.910575]
[25] Michael Luby, Michael Mitzenmacher, Amin Shokrollahi, and Daniel A. Spielman: Improved low-density parity-check codes using irregular graphs. IEEE Trans. Inform. Theory, 47(2):585–598, 2001. Preliminary versions in ISIT’98 and STOC’98. [doi:10.1109/18.910576]
[26] Judea Pearl: Reverend Bayes on inference engines: A distributed hierarchical approach. In Proc. 2nd Nat. Conf. on Artificial Intelligence (AAAI’82), pp. 133–136, 1982. AAAI.
[27] Thomas J. Richardson, Amin Shokrollahi, and Rüdiger L. Urbanke: Design of capacity-approaching irregular low-density parity-check codes. IEEE Trans. Inform. Theory, 47(2):619–637, 2001. [doi:10.1109/18.910578]