In this paper we analyze the performance of Warning Propagation, a popular message passing algorithm. We show that for 3CNF formulas drawn from a certain distribution over random satisfiable 3CNF formulas, commonly referred to as the planted-assignment distribution, running Warning Propagation in the standard way (run message passing until convergence, simplify the formula according to the resulting assignment, and satisfy the remaining subformula, if necessary, using a simple "off the shelf" heuristic) results in a satisfying assignment when the clause-variable ratio is a sufficiently large constant.
As for relevant results in random graph theory, the seminal work of Alon and Kahale @cite_28 paved the road towards dealing with large-constant-degree planted distributions. @cite_28 present an algorithm that @math @math -colors planted @math -colorable graphs (the distribution of graphs generated by partitioning the @math vertices into @math equally-sized color classes, and including every edge connecting two different color classes with probability @math ; commonly denoted @math ) with a sufficiently large constant expected degree. Building upon the techniques introduced in @cite_28 , Chen and Frieze @cite_14 present an algorithm that 2-colors large constant degree planted 3-uniform bipartite hypergraphs, and Flaxman @cite_7 presents an algorithm for satisfying large-constant clause-variable ratio planted 3SAT instances.
@cite_28 @cite_14 @cite_7
2079035346 1898334569 1994098212
Let G3n,p,3 be a random 3-colorable graph on a set of 3n vertices generated as follows. First, split the vertices arbitrarily into three equal color classes, and then choose every pair of vertices of distinct color classes, randomly and independently, to be edges with probability p. We describe a polynomial-time algorithm that finds a proper 3-coloring of G3n,p,3 with high probability, whenever p @math c n, where c is a sufficiently large absolute constant. This settles a problem of Blum and Spencer, who asked if an algorithm can be designed that works almost surely for p @math polylog(n) n [J. Algorithms, 19 (1995), pp. 204--234]. The algorithm can be extended to produce optimal k-colorings of random k-colorable graphs in a similar model as well as in various related models. Implementation results show that the algorithm performs very well in practice even for moderate values of c. It is NP-Hard to find a proper 2-coloring of a given 2-colorable (bipartite) hypergraph H. We consider algorithms that will color such a hypergraph using few colors in polynomial time. The results of the paper can be summarized as follows: Let n denote the number of vertices of H and m the number of edges, (i) For bipartite hypergraphs of dimension k there is a polynomial time algorithm which produces a proper coloring using min ( O(n^ 1 - 1 k ),O((m n)^ 1 k - 1 ) )colors, (ii) For 3-uniform bipartite hypergraphs, the bound is reduced to O(n2 9). (iii) For a class of dense 3-uniform bipartite hypergraphs, we have a randomized algorithm which can color optimally. (iv) For a model of random bipartite hypergraphs with edge probability p≥ dn−2, d > O a sufficiently large constant, we can almost surely find a proper 2-coloring. Let I be a random 3CNF formula generated by choosing a truth assignment φ for variables x 1 , ..., x n uniformly at random and including every clause with i literals set true by φ with probability p i , independently. We show that for any 0 ≤ η 2 , η 3 ≤ 1 there is a constant d min so that for all d ≥ d min , a spectral algorithm similar to the graph coloring algorithm of [1] will find a satisfying assignment with high probability for p 1 = d n2, p 2 = η 2 d n2, and p3 = η 3 d n2. Appropriately setting η 2 and η 3 yields natural distributions on satisfiable 3CNFs, not-all-equal-sat 3CNFs, and exactly-one-sat 3CNFs.