We introduce a general framework to design and analyze algorithms for the problem of testing homomorphisms between finite groups in the low-soundness regime. In this regime, we give the first constant-query tests for various families of groups. These include tests for: (i) homomorphisms between arbitrary cyclic groups, (ii) homomorphisms between any finite group and $\mathbb{ Z}_p$, (iii) automorphisms of dihedral and symmetric groups, (iv) inner automorphisms of non-abelian finite simple groups and extraspecial groups, and (v) testing linear characters of $\mathrm{ GL}_n(\mathbb{ F}_q)$, and finite-dimensional Lie algebras over $\mathbb{ F}_q$. We also recover the result of Kiwi [TCS'03] for testing homomorphisms between $\mathbb{ F}_q^n$ and $\mathbb{ F}_q$. Prior to this work, such tests were only known for abelian groups with a constant maximal order (such as $\mathbb{ F}_q^n$). No tests were known for non-abelian groups. As an additional corollary, our framework gives combinatorial list decoding bounds for cyclic groups with list size dependence of $O(\varepsilon^{ -2})$ (for agreement parameter $\varepsilon$). This improves upon the currently best-known bound of $O(\varepsilon^{ -105})$ due to Dinur, Grigorescu, Kopparty, and Sudan [STOC'08], and Guo and Sudan [RANDOM'14].
Categories: cs.CC cs.DS math.CO