English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this paper we consider the problems of testing isomorphism of tensors,$p$-groups, cubic forms, algebras, and more, which arise from a variety ofareas, including machine learning, group theory, and cryptography. Theseproblems can all be cast as orbit problems on multi-way arrays under differentgroup actions. Our first two main results are:  1. All the aforementioned isomorphism problems are equivalent underpolynomial-time reductions, in conjunction with the recent results ofFutorny-Grochow-Sergeichuk (Lin. Alg. Appl., 2019).  2. Isomorphism of $d$-tensors reduces to isomorphism of 3-tensors, for any $d\geq 3$.  Our results suggest that these isomorphism problems form a rich and robustequivalence class, which we call Tensor Isomorphism-complete, or TI-complete.We then leverage the techniques used in the above results to prove twofirst-of-their-kind results for Group Isomorphism (GpI):  3. We give a reduction from GpI for $p$-groups of exponent $p$ and smallclass ($c < p$) to GpI for $p$-groups of exponent $p$ and class 2. The latterare widely believed to be the hardest cases of GpI, but as far as we know, thisis the first reduction from any more general class of groups to this class.  4. We give a search-to-decision reduction for isomorphism of $p$-groups ofexponent $p$ and class 2 in time $|G|^{O(\log \log |G|)}$. Whilesearch-to-decision reductions for Graph Isomorphism (GI) have been known formore than 40 years, as far as we know this is the first non-trivialsearch-to-decision reduction in the context of GpI.  Our main technique for (1), (3), and (4) is a linear-algebraic analogue ofthe classical graph coloring gadget, which was used to obtain thesearch-to-decision reduction for GI. This gadget construction may be ofindependent interest and utility. The technique for (2) gives a method forencoding an arbitrary tensor into an algebra.

Isomorphism problems for tensors, groups, and cubic forms: completeness and reductions