  Sometimes local search algorithms cannot efficiently find even local peaks.
To understand why, I look at the structure of ascents in fitness landscapes
from valued constraint satisfaction problems (VCSPs). Given a VCSP with a
constraint graph of treedepth $d$, I prove that from any initial assignment
there always exists an ascent of length $2^{d + 1} \cdot n$ to a local peak.
This means that short ascents always exist in fitness landscapes from
constraint graphs of logarithmic treedepth, and thus also for all VCSPs of
bounded treewidth. But this does not mean that local search algorithms will
always find and follow such short ascents in sparse VCSPs. I show that with
loglog treedepth, superpolynomial ascents exist; and for polylog treedepth,
there are initial assignments from which all ascents are superpolynomial.
Together, these results suggest that the study of sparse VCSPs can help us
better understand the barriers to efficient local search.
