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%DIFDELCMD < ]%%% . 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? We answer this question positively for graph coloring by identifying the property ofgirth-reducibility . We prove that every girth-reducible graph of average degree (1-o(1) )q \ln q is efficiently q-colorable and that the threshold for girth reducibility of random graphs coincides with the algorithmic barrier. Thus, we link the tractability of graph coloring up to the algorithmic barrier to a single structural property. Our main theorem actually extends to coloring k-uniform hypergraphs. As such, we believe that it is an important first step towards discovering the structural properties behind the tractability of arbitrary k-CSPs for constraint densities up to the algorithmic barrier. Our main technical contribution is to prove that, for every k \ge 2, every k-uniform hypergaph of degree \Delta and girth at least 5 is efficiently (1+o(1) )(k-1) (\Delta / \ln \Delta )^{ 1/(k-1) } -list colorable via a deterministic algorithm , which is a result of independent interest .
 %DIFDELCMD < ]%%% We show that, for every k \ge 2, every k-uniform hypergaph of degree \Delta and girth at least 5 is efficiently (1+o(1) )(k-1) (\Delta / \ln \Delta )^{ 1/(k-1) } -list colorable . As an application we obtain the currently best deterministic algorithm for list-coloring random hypergraphs of bounded average degree .
D
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
D
Achlioptas and Coja-Oghlan 2008
D
. 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? We answer this question positively for graph coloring by identifying the property of
D
girth-reducibility
R
. We prove that
We show that, for
D
girth-reducible graph of average degree (1-o(1) )q \ln q is efficiently q-colorable and that the threshold for girth reducibility of random graphs coincides with the algorithmic barrier. Thus, we link the tractability of graph coloring up to the algorithmic barrier to a single structural property. Our main theorem actually extends to coloring k-uniform hypergraphs. As such, we believe that it is an important first step towards discovering the structural properties behind the tractability of arbitrary k-CSPs for constraint densities up to the algorithmic barrier. Our main technical contribution is to prove that, for every
R
via a deterministic algorithm , which is a result of independent interest
. As an application we obtain the currently best deterministic algorithm for list-coloring random hypergraphs of bounded average degree