Relationship between clustering and algorithmic phase transitions in the random k-XORSAT model and its NP-complete extensions

Fabrizio Altarelli, Remi Monasson, Francesco Zamponi

We study the performances of stochastic heuristic search algorithms on Uniquely Extendible Constraint Satisfaction Problems with random inputs. We show that, for any heuristic pres…