# The Library

### Algorithmic barriers from phase transitions

Tools

Achlioptas, Dimitris and Coja-Oghlan, Amin
(2008)
*Algorithmic barriers from phase transitions.*
In: Foundations of Computer Science, 2008. FOCS '08., Philadelphia, PA , 25-28 Oct 2008 . Published in: Symposium on Foundations of Computer Science. Annual Proceedings
pp. 793-802.

**Full text not available from this repository.**

Official URL: http://dx.doi.org/10.1109/FOCS.2008.11

## Abstract

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 the simplicity of those algorithms, one would expect room for improvement. Yet, to date, no algorithm is known that uses (2 - epsiv)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 find it 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 speaking, we prove that the set of k-colorings looks like a giant ball for k ges 2chi, but like an error-correcting code for k les (2 - epsiv)chi. We also prove that an analogous phase transition occurs both in random k-SAT and in random hypergraph 2-coloring. And that for each of these three problems, the location of the transition corresponds to the point where all known polynomial-time algorithms fail. To prove our results we develop a general technique that allows us to establish rigorously much of the celebrated 1-step replica-symmetry-breaking hypothesis of statistical physics for random CSPs.

Item Type: | Conference Item (Paper) |
---|---|

Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |

Divisions: | Faculty of Science > Computer Science Faculty of Science > Mathematics |

Journal or Publication Title: | Symposium on Foundations of Computer Science. Annual Proceedings |

Publisher: | IEEE Computer Society |

ISSN: | 1523-8288 |

Book Title: | 2008 49th Annual IEEE Symposium on Foundations of Computer Science |

Date: | 2008 |

Page Range: | pp. 793-802 |

Identification Number: | 10.1109/FOCS.2008.11 |

Status: | Peer Reviewed |

Publication Status: | Published |

Access rights to Published version: | Restricted or Subscription Access |

Conference Paper Type: | Paper |

Title of Event: | Foundations of Computer Science, 2008. FOCS '08. |

Type of Event: | Other |

Location of Event: | Philadelphia, PA |

Date(s) of Event: | 25-28 Oct 2008 |

URI: | http://wrap.warwick.ac.uk/id/eprint/42232 |

### Actions (login required)

View Item |