Identify a string x over {0,1} with the positive integer
whose binary representation is 1x. We say that a self-reduction is
k-local if on input x all queries belong to {x-1,...,x-k}. We show
that all k-locally self-reducible sets belong to PSPACE. However, the
power of k-local self-reductions changes drastically between k=2 and
k=3. Although all 2-locally self-reducible sets belong to MOD6PH,
some 3-locally self-reducible sets are PSPACE-complete. Furthermore,
there exists a 6-locally self-reducible PSPACE-complete set whose
self-reduction is an m-reduction (in fact, a permutation).

We prove all these results by showing that such languages are
equivalent in complexity to the problem of multiplying an
exponentially long sequence of uniformly generated elements in a
finite monoid, and then exploiting the algebraic structure of the
monoid.