Algorithmic Barriers from Phase Transitions
For many random Constraint Satisfaction Problems, by ntnv theiv 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 - ε)x 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,.... kn, 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 ≥ 2X, but like an errorcorrecting code for k ≤ (2 - ε)X. 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 muck of the celebrated 1-step Replica-SymmetryBreaking hypothesis of statistical physics for random CSPs.
Dimitris Achlioptas Amin Coja-Oghlan
UC Santa Cruz. Santa Cruz, CA 95064. USA and CTI, Greece. Supported by NSF CAREER award CCF-0546900, School of Informatics. University of Edinburgh, UK. Supported by OFGCO646
国际会议
International Workshop on Statistical Physics and Computer Sciences(统计物理与计算机科学交叉研究国际研讨会 )
北京
英文
1-10
2010-07-08（万方平台首次上网日期，不代表论文的发表时间）