  We connect the mixing behaviour of random walks over a graph to the power of
the local-consistency algorithm for the solution of the corresponding
constraint satisfaction problem (CSP). We extend this connection to arbitrary
CSPs and their promise variant. In this way, we establish a linear-level (and,
thus, optimal) lower bound against the local-consistency algorithm applied to
the class of aperiodic promise CSPs. The proof is based on a combination of the
probabilistic method for random Erd\H{o}s-R\'enyi hypergraphs and a structural
result on the number of fibers (i.e., long chains of hyperedges) in sparse
hypergraphs of large girth. As a corollary, we completely classify the power of
local consistency for the approximate graph homomorphism problem by
establishing that, in the nontrivial cases, the problem has linear width.
