{"ID":2873671,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.05871","arxiv_id":"2509.05871","title":"A General Framework for Low Soundness Homomorphism Testing","abstract":"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].","short_abstract":"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,...","url_abs":"https://arxiv.org/abs/2509.05871","url_pdf":"https://arxiv.org/pdf/2509.05871v1","authors":"[\"Tushant Mittal\",\"Sourya Roy\"]","published":"2025-09-07T00:00:35Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.DS\",\"math.CO\"]","methods":"[]","has_code":false}