A General Framework for Low Soundness Homomorphism Testing
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915483187412992 |
|---|---|
| author | Mittal, Tushant Roy, Sourya |
| author_facet | Mittal, Tushant Roy, Sourya |
| contents | 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]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_05871 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A General Framework for Low Soundness Homomorphism Testing Mittal, Tushant Roy, Sourya Computational Complexity Data Structures and Algorithms Combinatorics 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]. |
| title | A General Framework for Low Soundness Homomorphism Testing |
| topic | Computational Complexity Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2509.05871 |