Open Collections

Tensor Isomorphism: completeness, graph-theoretic methods, and consequences for Group Isomorphism

Banff International Research Station for Mathematical Innovation and Discovery

We consider the problems of testing isomorphism of tensors, p-groups, cubic forms, algebras, and more, which arise from a variety of areas, including machine learning, group theory, and cryptography. Despite a perhaps seeming similarity with Graph Isomorphism, the current-best algorithms for these problems (when given by bases) are still exponential - for most of them, even q^{n^2} over GF(q). Similarly, while efficient practical software exists for Graph Isomorphism, for these problems even the best current software can only handle very small instances (e.g., 10 x 10 x 10 over GF(13)). This raises the question of finding new algorithmic techniques for these problems, and/or of proving hardness results. We show that all of these problems are equivalent under polynomial-time reductions, giving rise to a class of problems we call Tensor Isomorphism-complete (TI-complete). We further show that testing isomorphism of d-tensors for any fixed d (at least 3) is equivalent to testing isomorphism of 3-tensors. Using the same techniques, we show two first-of-their-kind results for Group Isomorphism (GpI): (a) a reduction from isomorphism of p-groups of exponent p and class c < p, to isomorphism of p-groups of exponent p and class 2, and (b) a search-to-decision reduction for the latter class of groups in time |G|^{O(log log|G|)}. We note that while p-groups of class 2 have long been believed to be the hardest cases of GpI, as far as we are aware this is the first reduction from any larger class to this class of groups. Finally, we discuss a way to apply combinatorial methods from Graph Isomorphism (namely, Weisfeiler-Leman) to Group and Tensor Isomorphism. Based on joint works with Vyacheslav V. Futorny and Vladimir V. Sergeichuk (Lin. Alg. Appl., 2019; arXiv:1810.09219), with Peter A. Brooksbank, Yinan Li, Youming Qiao, and James B. Wilson (arXiv:1905.02518), and with Youming Qiao (arXiv:190X.XXXXX).

Mathematics; Computer science; Theoretical computer science

video/mp4

Author affiliation: University of Colorado at Boulder

2020-01-09

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/73238

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/