  Modern distributed computation infrastructures are often plagued by
unavailabilities such as failing or slow servers. These unavailabilities
adversely affect the tail latency of computation in distributed
infrastructures. The simple solution of replicating computation entails
significant resource overhead. Coded computation has emerged as a
resource-efficient alternative, wherein multiple units of data are encoded to
create parity units and the function to be computed is applied to each of these
units on distinct servers. A decoder can use the available function outputs to
decode the unavailable ones. Existing coded computation approaches are resource
efficient only for simple variants of linear functions such as multilinear,
with even the class of low degree polynomials requiring the same multiplicative
overhead as replication for practically relevant straggler tolerance.
  In this paper, we present a new approach to model coded computation via the
lens of locality of codes. We introduce a generalized notion of locality,
denoted computational locality, building upon the locality of an appropriately
defined code. We show that computational locality is equivalent to the required
number of workers for coded computation and leverage results from the
well-studied locality of codes to design coded computation schemes. We show
that recent results on coded computation of multivariate polynomials can be
derived using local recovering schemes for Reed-Muller codes. We present coded
computation schemes for multivariate polynomials that adaptively exploit
locality properties of input data-- an inadmissible technique under existing
frameworks. These schemes require fewer workers than the lower bound under
existing coded computation frameworks, showing that the existing multiplicative
overhead on the number of servers is not fundamental for coded computation of
nonlinear functions.
