research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:
TitleAlgorithmic Barriers from Phase Transitions in Graphs
Bibtex cite IDRACTI-RU1-2010-45
Booktitle 36th International Workshop on Graph Theoretic
Year published 2010
Month June
For a number of optimization problems on random graphs and hypergraphs, e.g., k-colorings, there is a very big gap between the largest average degree for which known polynomial-time algorithms can find solutions, and the largest average degree for which solutions provably exist. We study this phenomenon by examining how sets of solutions evolve as edges are added.We prove in a precise mathematical sense that, for each problem studied, the barrier faced by algorithms corresponds to a phase transition in the problems solution-space geometry. Roughly speaking, at some problem-specific critical density, the set of solutions shatters and goes from being a single giant ball to exponentially many, well-separated, tiny pieces. All known polynomial-time algorithms work in the ball regime, but stop as soon as the shattering occurs. Besides giving a geometric view of the solution space of random instances our results provide novel constructions of one-way functions.
Achlioptas, Dimitris
fulltext.pdf (main file)
Publication ID814