The Library
Algorithmic barriers from phase transitions
Tools
Achlioptas, Dimitris and CojaOghlan, Amin (2008) Algorithmic barriers from phase transitions. In: Foundations of Computer Science, 2008. FOCS '08., Philadelphia, PA , 2528 Oct 2008 . Published in: Symposium on Foundations of Computer Science. Annual Proceedings pp. 793802.
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 polynomialtime algorithms stop finding solutions at much smaller densities. For example, it is wellknown 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 kcolorings 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 kcolorings looks like a giant ball for k ges 2chi, but like an errorcorrecting code for k les (2  epsiv)chi. We also prove that an analogous phase transition occurs both in random kSAT and in random hypergraph 2coloring. And that for each of these three problems, the location of the transition corresponds to the point where all known polynomialtime algorithms fail. To prove our results we develop a general technique that allows us to establish rigorously much of the celebrated 1step replicasymmetrybreaking 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:  15238288  
Book Title:  2008 49th Annual IEEE Symposium on Foundations of Computer Science  
Official Date:  2008  
Dates: 


Page Range:  pp. 793802  
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:  2528 Oct 2008  
URI:  http://wrap.warwick.ac.uk/id/eprint/42232 
Request changes or add full text files to a record
Actions (login required)
View Item 