Algorithmic barriers from phase transitions

Abstract

For many random Constraint Satisfaction Problems, by now, we have asymptotically tight estimates of the largest constraint density for which they have solutions. At the same time, all known polynomial-time algorithms for many of these problems already completely fail to find solutions at much smaller densities. For example, it is well-known that it is easy to color a random graph using twice as many colors as its chromatic number. Indeed, some of the simplest possible coloring algorithms already achieve this goal. Given the simplicity of those algorithms, one would expect there is a lot of room for improvement. Yet, to date, no algorithm is known that uses $(2-\epsilon )\chi$ colors, in spite of efforts by numerous researchers over the years. In view of the remarkable resilience of this factor of 2 against every algorithm hurled at it, we believe it is natural to inquire into its origin. We do so by analyzing the evolution of the set of $k$-colorings of a random graph, viewed as a subset of $\{1,...,k{\}}^n$, as edges are added. We prove that the factor of 2 corresponds in a precise mathematical sense to a phase transition in the geometry of this set. Roughly, the set of $k$-colorings looks like a giant ball for $k\ge 2\chi$, but like an error-correcting code for $k\le (2-\epsilon )\chi$. We prove that a completely analogous phase transition also occurs both in random $k$-SAT and in random hypergraph 2-coloring. And that for each problem, its location corresponds precisely with the point were all known polynomial-time algorithms fail. To prove our results we develop a general technique that allows us to prove rigorously much of the celebrated 1-step Replica-Symmetry-Breaking hypothesis of statistical physics for random CSPs.

extended abstract

References in corpus (4)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Clustering of solutions in the random satisfiability problem
• Polynomial iterative algorithms for coloring and analyzing random graphs
• Minimizing energy below the glass thresholds

Cited by in corpus (30)

• Consistency of Spectral Hypergraph Partitioning under Planted Partition Model
• The backtracking survey propagation algorithm for solving random K-SAT problems
• Catching the k-NAESAT Threshold
• Computational Barriers to Estimation from Low-Degree Polynomials
• The condensation phase transition in random graph coloring
• Spectral Detection on Sparse Hypergraphs
• Charting the replica symmetric phase
• Information-theoretic and algorithmic thresholds for group testing
• Going after the k-SAT Threshold
• Harnessing the Bethe free energy
• A positive temperature phase transition in random hypergraph 2-coloring
• Metastability of the Potts ferromagnet on random regular graphs
• Phase transition for the mixing time of the Glauber dynamics for coloring regular trees
• The set of solutions of random XORSAT formulae
• The replica symmetric phase of random constraint satisfaction problems
• Planting colourings silently
• Dense Hopfield Networks in the Teacher-Student Setting
• Tractability from overparametrization: The example of the negative perceptron
• The Tightness of the Kesten-Stigum Reconstruction Bound of Symmetric Model with Multiple Mutations
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials
• Collective dynamics in a glass-former with Mari-Kurchan interactions
• The asymptotics of the clustering transition for random constraint satisfaction problems
• Combinatorial NLTS From the Overlap Gap Property
• An exact algorithm exhibiting RS-RSB/easy-hard correspondence for the maximum independent set problem
• Extremal bipartite independence number and balanced coloring
• Parallel Complexity of Random Boolean Circuits
• Constructing Concrete Hard Instances of the Maximum Independent Set Problem
• Uniformly Random Colourings of Sparse Graphs
• The Forgetfulness of Balls and Bins
• Deterministic counting of graph colourings using sequences of subgraphs