2026-07-21T20:03:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13570 2024-03-06T10:52:20Z ddc:004 open_access

On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness Grochow, Joshua A. Qiao, Youming complexity class tensor isomorphism polynomial isomorphism group isomorphism stochastic local operations and classical communication We study the complexity of isomorphism problems for tensors, groups, and polynomials. These problems have been studied in multivariate cryptography, machine learning, quantum information, and computational group theory. We show that these problems are all polynomial-time equivalent, creating bridges between problems traditionally studied in myriad research areas. This prompts us to define the complexity class TI, namely problems that reduce to the Tensor Isomorphism (TI) problem in polynomial time. Our main technical result is a polynomial-time reduction from d-tensor isomorphism to 3-tensor isomorphism. In the context of quantum information, this result gives multipartite-to-tripartite entanglement transformation procedure, that preserves equivalence under stochastic local operations and classical communication (SLOCC). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Joshua A. Grochow and Youming Qiao 2021 Is Part Of LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2021.31 urn:nbn:de:0030-drops-135702 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.31 eng https://creativecommons.org/licenses/by/3.0/legalcode