  Consider a distributed coding for computing problem with constant decoding
locality, i.e., with a vanishing error probability, any single sample of the
function can be approximately recovered by probing only constant number of
compressed bits. We establish an achievable rate region by designing an
efficient layered coding scheme, where the coding rate is reduced by
introducing auxiliary random variables and local decoding is achieved by
exploiting the expander graph code. Then we show the rate region is optimal
under mild regularity conditions on source distributions. The proof relies on
the reverse hypercontractivity and a rounding technique to construct auxiliary
random variables. The rate region is strictly smaller than that for the
classical problem without the constant locality constraint in most cases, which
indicates that more rate is required in order to achieve lower coding
complexity. Moreover, a coding for computing problem with side information is
analogously studied. We also develop graph characterizations, which simplifies
the computation of the achievable rate region.
