2026-09-20T12:50:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25390 2026-09-05T19:15:22Z ddc:004 open_access

A General Framework for Low Soundness Homomorphism Testing Mittal, Tushant Roy, Sourya Property Testing Coding Theory 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 ℤ_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 GL_n(F_q), and finite-dimensional Lie algebras over F_q. We also recover the result of Kiwi [TCS'03] for testing homomorphisms between F_qⁿ and F_q. Prior to this work, such tests were only known for abelian groups with a constant maximal order (such as F_qⁿ). 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(ε^{-2}) (for agreement parameter ε). This improves upon the currently best-known bound of O(ε^{-105}) due to Dinur, Grigorescu, Kopparty, and Sudan [STOC'08], and Guo and Sudan [RANDOM'14]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tushant Mittal and Sourya Roy 2026 Is Part Of LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2026.103 urn:nbn:de:0030-drops-253901 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.103 eng https://creativecommons.org/licenses/by/4.0/legalcode