On the complexity of isomorphism problems for tensors, groups, and polynomials IV: linear-length reductions and their applications
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916202969825280 |
|---|---|
| author | Grochow, Joshua A. Qiao, Youming |
| author_facet | Grochow, Joshua A. Qiao, Youming |
| contents | Many isomorphism problems for tensors, groups, algebras, and polynomials were recently shown to be equivalent to one another under polynomial-time reductions, prompting the introduction of the complexity class TI (Grochow & Qiao, ITCS '21; SIAM J. Comp., '23). Using the tensorial viewpoint, Grochow & Qiao (CCC '21) then gave moderately exponential-time search- and counting-to-decision reductions for a class of $p$-groups. A significant issue was that the reductions usually incurred a quadratic increase in the length of the tensors involved. When the tensors represent $p$-groups, this corresponds to an increase in the order of the group of the form $|G|^{Θ(\log |G|)}$, negating any asymptotic gains in the Cayley table model.
In this paper, we present a new kind of tensor gadget that allows us to replace those quadratic-length reductions with linear-length ones, yielding the following consequences:
1. If Graph Isomorphism is in P, then testing equivalence of cubic forms in $n$ variables over $F_q$, and testing isomorphism of $n$-dimensional algebras over $F_q$, can both be solved in time $q^{O(n)}$, improving from the brute-force upper bound $q^{O(n^2)}$ for both of these.
2. Combined with the $|G|^{O((\log |G|)^{5/6})}$-time isomorphism-test for $p$-groups of class 2 and exponent $p$ (Sun, STOC '23), our reductions extend this runtime to $p$-groups of class $c$ and exponent $p$ where $c<p$, and yield algorithms in time $q^{O(n^{1.8}\cdot \log q)}$ for cubic form equivalence and algebra isomorphism.
3. Polynomial-time search- and counting-to-decision reduction for testing isomorphism of $p$-groups of class $2$ and exponent $p$ when Cayley tables are given. This answers questions of Arvind and Tóran (Bull. EATCS, 2005) for this group class, thought to be one of the hardest cases of Group Isomorphism. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_16317 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On the complexity of isomorphism problems for tensors, groups, and polynomials IV: linear-length reductions and their applications Grochow, Joshua A. Qiao, Youming Computational Complexity Data Structures and Algorithms Algebraic Geometry Group Theory 68Q25, 15A69, 15A72, 15A21, 15A63, 68Q15, 16Z05, 17B99, 17A40, 20D15, 20-08 F.1.3; F.2.2; I.1.2 Many isomorphism problems for tensors, groups, algebras, and polynomials were recently shown to be equivalent to one another under polynomial-time reductions, prompting the introduction of the complexity class TI (Grochow & Qiao, ITCS '21; SIAM J. Comp., '23). Using the tensorial viewpoint, Grochow & Qiao (CCC '21) then gave moderately exponential-time search- and counting-to-decision reductions for a class of $p$-groups. A significant issue was that the reductions usually incurred a quadratic increase in the length of the tensors involved. When the tensors represent $p$-groups, this corresponds to an increase in the order of the group of the form $|G|^{Θ(\log |G|)}$, negating any asymptotic gains in the Cayley table model. In this paper, we present a new kind of tensor gadget that allows us to replace those quadratic-length reductions with linear-length ones, yielding the following consequences: 1. If Graph Isomorphism is in P, then testing equivalence of cubic forms in $n$ variables over $F_q$, and testing isomorphism of $n$-dimensional algebras over $F_q$, can both be solved in time $q^{O(n)}$, improving from the brute-force upper bound $q^{O(n^2)}$ for both of these. 2. Combined with the $|G|^{O((\log |G|)^{5/6})}$-time isomorphism-test for $p$-groups of class 2 and exponent $p$ (Sun, STOC '23), our reductions extend this runtime to $p$-groups of class $c$ and exponent $p$ where $c<p$, and yield algorithms in time $q^{O(n^{1.8}\cdot \log q)}$ for cubic form equivalence and algebra isomorphism. 3. Polynomial-time search- and counting-to-decision reduction for testing isomorphism of $p$-groups of class $2$ and exponent $p$ when Cayley tables are given. This answers questions of Arvind and Tóran (Bull. EATCS, 2005) for this group class, thought to be one of the hardest cases of Group Isomorphism. |
| title | On the complexity of isomorphism problems for tensors, groups, and polynomials IV: linear-length reductions and their applications |
| topic | Computational Complexity Data Structures and Algorithms Algebraic Geometry Group Theory 68Q25, 15A69, 15A72, 15A21, 15A63, 68Q15, 16Z05, 17B99, 17A40, 20D15, 20-08 F.1.3; F.2.2; I.1.2 |
| url | https://arxiv.org/abs/2306.16317 |