  We define the Homomorphism Extension (HomExt) problem: given a group $G$, a
subgroup $M \leq G$ and a homomorphism $\varphi: M \to H$, decide whether or
not there exists a homomorphism $\widetilde{\varphi}: G\to H$ extending
$\varphi$, i.e., $\widetilde{\varphi}|_M = \varphi$. This problem arose in the
context of list-decoding homomorphism codes but is also of independent
interest, both as a problem in computational group theory and as a new and
natural problem in NP of unsettled complexity status.
  We consider the case $H=S_m$ (the symmetric group of degree $m$), i.e.,
$\varphi : G \to H$ is a $G$-action on a set of $m$ elements. We assume $G\le
S_n$ is given as a permutation group by a list of generators. We characterize
the equivalence classes of extensions in terms of a multidimensional oracle
subset-sum problem. From this we infer that for bounded $G$ the HomExt problem
can be solved in polynomial time.
  Our main result concerns the case $G=A_n$ (the alternating group of degree
$n$) for variable $n$ under the assumption that the index of $M$ in $G$ is
bounded by poly$(n)$. We solve this case in polynomial time for all $m <
2^{n-1}/\sqrt{n}$. This is the case with direct relevance to homomorphism codes
(Babai, Black, and Wuu, arXiv 2018); it is used as a component of one of the
main algorithms in that paper.
