  The XOR-satisfiability (XORSAT) problem requires finding an assignment of $n$
Boolean variables that satisfy $m$ exclusive OR (XOR) clauses, whereby each
clause constrains a subset of the variables. We consider random XORSAT
instances, drawn uniformly at random from the ensemble of formulae containing
$n$ variables and $m$ clauses of size $k$. This model presents several
structural similarities to other ensembles of constraint satisfaction problems,
such as $k$-satisfiability ($k$-SAT), hypergraph bicoloring and graph coloring.
For many of these ensembles, as the number of constraints per variable grows,
the set of solutions shatters into an exponential number of well-separated
components. This phenomenon appears to be related to the difficulty of solving
random instances of such problems. We prove a complete characterization of this
clustering phase transition for random $k$-XORSAT. In particular, we prove that
the clustering threshold is sharp and determine its exact location. We prove
that the set of solutions has large conductance below this threshold and that
each of the clusters has large conductance above the same threshold. Our proof
constructs a very sparse basis for the set of solutions (or the subset within a
cluster). This construction is intimately tied to the construction of specific
subgraphs of the hypergraph associated with an instance of $k$-XORSAT. In order
to study such subgraphs, we establish novel local weak convergence results for
them.
