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. doi:10.1109/FOCS.2008.11 ISSN 1523-8288.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
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, Engineering and Medicine > Science > Computer Science Faculty of Science, Engineering and Medicine > 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 | ||||
Official Date: | 2008 | ||||
Dates: |
|
||||
Page Range: | pp. 793-802 | ||||
DOI: | 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 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |