Before revision: All known efficient algorithms for constraint satisfaction problems are stymied by random instances. For example, no efficient algorithm is known that can q-color a random graph with average degree (1 + \epsilon)q \ln q, even though random graphs remain q-colorable for average degree up to (2-o(1)) q \ln q. Similar failure to find solutions at relatively low constraint densities is known for random CSPs such as random k-SAT and other hypergraph-based problems. The constraint density where algorithms break down for each CSP is known as the "algorithmic barrier" and provably corresponds to a phase transition in the geometry of the space of solutions Achlioptas and Coja-Oghlan 2008 . In this paper we aim to shed light on the following question: Can algorithmic success up to the barrier for each CSP be ascribed to some simple structural property of the inputs?
After revision:  Achlioptas and Coja-Oghlan 2008 . In this paper we aim to shed light on the following question: Can algorithmic success up to the barrier for each CSP be ascribed to some simple structural property of the inputs?