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.

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

Request changes to a record

Actions (login required)

View Item