Document

**Published in:** LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Let vec(theta) be a uniformly distributed random k-SAT formula with n variables and m clauses. For clauses/variables ratio m/n <= r_{k-SAT} ~ 2^k*ln(2) the formula vec(theta) is satisfiable with high probability. However, no efficient algorithm is known to provably find a satisfying assignment beyond m/n ~ 2k*ln(k)/k with a non-vanishing probability. Non-rigorous statistical mechanics work on k-CNF led to the development of a new efficient "message passing algorithm" called Survey Propagation Guided Decimation [Mézard et al., Science 2002]. Experiments conducted for k=3,4,5 suggest that the algorithm finds satisfying assignments close to r_{k-SAT}. However, in the present paper we prove that the basic version of Survey Propagation Guided Decimation fails to solve random k-SAT formulas efficiently already for m/n = 2^{k}(1 + epsilon_k)*ln(k)/k with lim_{k -> infinity} epsilon_k = 0 almost a factor k below r_{k-SAT}.

Samuel Hetterich. Analysing Survey Propagation Guided Decimationon Random Formulas. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 65:1-65:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{hetterich:LIPIcs.ICALP.2016.65, author = {Hetterich, Samuel}, title = {{Analysing Survey Propagation Guided Decimationon Random Formulas}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {65:1--65:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.65}, URN = {urn:nbn:de:0030-drops-62197}, doi = {10.4230/LIPIcs.ICALP.2016.65}, annote = {Keywords: Survey Propagation Guided Decimation, Message Passing Algorithm, Graph Theory, Random k-SAT} }

Document

**Published in:** LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Based on a non-rigorous formalism called the "cavity method", physicists have put forward intriguing predictions on phase transitions in discrete structures. One of the most remarkable ones is that in problems such as random k-SAT or random graph k-coloring, very shortly before the threshold for the existence of solutions there occurs another phase transition called condensation [Krzakala et al., PNAS 2007]. The existence of this phase transition appears to be intimately related to the difficulty of proving precise results on, e.g., the k-colorability threshold as well as to the performance of message passing algorithms. In random graph k-coloring, there is a precise conjecture as to the location of the condensation phase transition in terms of a distributional fixed point problem. In this paper we prove this conjecture for k exceeding a certain constant k0.

Victor Bapst, Amin Coja-Oghlan, Samuel Hetterich, Felicia Raßmann, and Dan Vilenchik. The Condensation Phase Transition in Random Graph Coloring. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 449-464, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{bapst_et_al:LIPIcs.APPROX-RANDOM.2014.449, author = {Bapst, Victor and Coja-Oghlan, Amin and Hetterich, Samuel and Ra{\ss}mann, Felicia and Vilenchik, Dan}, title = {{The Condensation Phase Transition in Random Graph Coloring}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)}, pages = {449--464}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-74-3}, ISSN = {1868-8969}, year = {2014}, volume = {28}, editor = {Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.449}, URN = {urn:nbn:de:0030-drops-47168}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.449}, annote = {Keywords: random graphs, graph coloring, phase transitions, message-passing algorithm} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail