# Algorithmic Barriers from Phase Transitions

@article{Achlioptas2008AlgorithmicBF, title={Algorithmic Barriers from Phase Transitions}, author={Dimitris Achlioptas and Amin Coja-Oghlan}, journal={2008 49th Annual IEEE Symposium on Foundations of Computer Science}, year={2008}, pages={793-802} }

For many random constraint satisfaction problems, by now there exist asymptotically tight estimates of the largest constraint density for which solutions exist. At the same time, for many of these problems, all known polynomial-time algorithms stop finding 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 achieve this goal. Given… Expand

#### Topics from this paper

#### Paper Mentions

#### 236 Citations

On the solution-space geometry of random constraint satisfaction problems

- Mathematics, Computer Science
- STOC '06
- 2006

It is proved that much before solutions disappear, they organize into an exponential number of clusters, each of which is relatively small and far apart from all other clusters, which gives a satisfying intuitive explanation for the failure of the polynomial-time algorithms analyzed so far. Expand

Girth-reducibility and the algorithmic barrier for coloring

- Mathematics, Computer Science
- ArXiv
- 2020

It is proved that every girth-reducible graph of average degree $(1-o(1) )q \ln q$ is efficiently-colorable and that the threshold for girth reducibility of random graphs coincides with the algorithmic barrier, which links the tractability of graph coloring up to the algorithm barrier to a single structural property. Expand

The condensation transition in random hypergraph 2-coloring

- Mathematics, Physics
- SODA
- 2012

This paper proves for the first time that a condensation transition exists in a natural random CSP, namely in random hypergraph 2-coloring, and finds that the second moment method applied to the number of 2-colorings breaks down strictly before the condensation Transition. Expand

The condensation phase transition in random graph coloring

- Computer Science, Mathematics
- ArXiv
- 2014

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, and this paper proves this conjecture for k exceeding a certain constant k0. Expand

Phase transitions in the $q$-coloring of random hypergraphs

- Mathematics, Computer Science
- ArXiv
- 2017

This work provides explicit values and predictions for a number of phase transitions that were discovered in other constraint satisfaction problems but never evaluated before in hypergraph coloring. Expand

Complexity of Coloring Random Graphs

- Mathematics, Computer Science
- ACM J. Exp. Algorithmics
- 2018

This article uses list coloring to model coloring with a fractional number of colors between χ − 1 and χ and turns out that the complexity follows an alternating three-dimensional pattern; understanding this pattern is very important for benchmarking purposes. Expand

Reconstruction and Clustering in Random Constraint Satisfaction Problems

- Mathematics, Computer Science
- SIAM J. Discret. Math.
- 2011

A set of technical conditions are formulated on a large family of random CSPs and bounds are proved on three most interesting thresholds for the density of such an ensemble: namely, the satisfiability threshold, the threshold for clustering of the solution space, and thereshold for an appropriate reconstruction problem on the CSPS. Expand

On percolation and -hardness

- Mathematics, Computer Science
- Random Struct. Algorithms
- 2019

It is proved that for n-vertex graphs, these problems remain as hard as in the worst-case, as long as p > 1 n1− for arbitrary ∈ (0, 1), unless NP ⊆ BPP. Expand

Going after the k-SAT threshold

- Mathematics, Computer Science
- STOC '13
- 2013

A new asymmetric second moment method is developed that allows us to tackle the k-SAT threshold head on for the first time in the theory of random CSPs and matches the best bound that can be obtained from the so-called "replica symmetric" version of the cavity method. Expand

Low-Degree Hardness of Random Optimization Problems

- Computer Science, Physics
- 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)
- 2020

This work considers the problem of finding nearly optimal solutions of optimization problems with random objective functions and considers the Langevin dynamics algorithm, a canonical Monte Carlo analogue of the gradient descent algorithm (applicable only for the spherical p-spin glass Hamiltonian). Expand

#### References

SHOWING 1-10 OF 37 REFERENCES

On the solution-space geometry of random constraint satisfaction problems

- Mathematics, Computer Science
- STOC '06
- 2006

It is proved that much before solutions disappear, they organize into an exponential number of clusters, each of which is relatively small and far apart from all other clusters, which gives a satisfying intuitive explanation for the failure of the polynomial-time algorithms analyzed so far. Expand

Rigorous location of phase transitions in hard optimization problems

- Computer Science, Medicine
- Nature
- 2005

The results prove that the heuristic predictions of statistical physics in this context are essentially correct and establish that random instances of constraint satisfaction problems have solutions well beyond the reach of any analysed algorithm. Expand

Polynomial iterative algorithms for coloring and analyzing random graphs.

- Mathematics, Physics
- Physical review. E, Statistical, nonlinear, and soft matter physics
- 2003

It is found that graphs with low connectivity admit almost always a proper coloring whereas graphs with high connectivity are uncolorable, which leads to a different algorithm that is able to color in polynomial time random graphs in the hard but colorable region. Expand

Why Almost All k -Colorable Graphs Are Easy

- Mathematics, Computer Science
- STACS
- 2007

This work rigorously shows that all proper k- colorings of most such graphs are clustered in one cluster, and agree on all but a small, though constant, number of vertices. Expand

The analysis of a list-coloring algorithm on a random graph

- Mathematics, Computer Science
- Proceedings 38th Annual Symposium on Foundations of Computer Science
- 1997

A natural k-coloring algorithm is introduced and its performance on random graphs with constant expected degree c is analyzed to improve the lower bound on the threshold for random 3-colorability significantly and settles the last case of a long-standing open question of Bollobas. Expand

Sharp thresholds of graph properties, and the -sat problem

- Mathematics
- 1999

Consider G(n, p) to be the probability space of random graphs on n vertices with edge probability p. We will be considering subsets of this space defined by monotone graph properties. A monotone… Expand

Random k-SAT: Two Moments Suffice to Cross a Sharp Threshold

- Mathematics, Computer Science
- SIAM J. Comput.
- 2006

It is proved that the threshold for both random hypergraph 2-colorability and random Not-All-Equal $k$-SAT is $2^{k-1}\ln 2 -O(1)$, resolving a long-standing open problem. Expand

Reconstruction for Models on Random Graphs

- Mathematics, Physics
- 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07)
- 2007

A sufficient condition for the tree and graph reconstruction problem to coincide is developed and applied to colorings of random graphs, which are sequences of random graph sequences that converge locally to trees. Expand

Reconstruction for Models on Random Graphs

- Mathematics
- FOCS 2007
- 2007

Consider a collection of random variables attached to the vertices of a graph. The reconstruction problem requires to estimate one of them given far away' observations. Several theoretical results… Expand

Gibbs states and the set of solutions of random constraint satisfaction problems

- Mathematics, Computer Science
- Proceedings of the National Academy of Sciences
- 2007

Empirical evidence suggests that local Monte Carlo Markov chain strategies are effective up to the clustering phase transition and belief propagation up toThe condensation point and refined message passing techniques (such as survey propagation) may also beat this threshold. Expand