Homomorphism Extension

Abstract

We define the Homomorphism Extension (HomExt) problem: given a group $G$, a subgroup $M\le G$ and a homomorphism $\phi :M\to H$, decide whether or not there exists a homomorphism $\tilde{\phi }:G\to H$ extending $\phi$, i.e., $\tilde{\phi }{|}_M=\phi$. 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., $\phi :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.

29 pages

References in corpus (1)

• List decoding group homomorphisms between supersolvable groups