Universality in polytope phase transitions and iterative algorithms.
Mohsen BayatiMarc LelargeAndrea MontanariPublished in: ISIT (2012)
Keyphrases
- iterative algorithms
- phase transition
- hamiltonian cycle
- cellular automata
- lattice points
- constraint satisfaction
- satisfiability problem
- stable set
- random constraint satisfaction problems
- combinatorial problems
- randomly generated
- np complete
- convex hull
- graph coloring
- random instances
- hard problems
- sat problem
- random graphs
- stochastic local search
- iterative methods
- np complete problems
- dual formulation
- search algorithm