On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness
From MaRDI portal
Publication:5890037
DOI10.1137/21M1441110OpenAlexW4367041818MaRDI QIDQ5890037
Youming Qiao, Joshua A. Grochow
Publication date: 28 April 2023
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/21m1441110
completenessgroup isomorphismisomorphism problemspolynomial isomorphismcomplexity classtensor isomorphism
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Quantum information, communication, networks (quantum-theoretic aspects) (81P45)
Related Items (2)
General linear group action on tensors: a candidate for post-quantum cryptography ⋮ Graph-theoretic algorithms for the alternating trilinear form equivalence problem
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Tensor Decompositions and Applications
- The module isomorphism problem reconsidered.
- Complexity classes of equivalence problems revisited
- Integration of paths, geometric invariants and a generalized Baker-Hausdorff formula
- Testing isomorphism of modules.
- Invariance of simultaneous similarity and equivalence of matrices under extension of the ground field
- Decomposing \(p\)-groups via Jordan algebras.
- Graph isomorphism problem
- Sweeping-similarity of matrices
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- Isomorphism testing for \(p\)-groups
- The Magma algebra system. I: The user language
- Automorphism group computation and isomorphism testing in finite groups
- Canonical matrices for linear matrix problems
- Inverting the signature of a path
- Wildness for tensors
- Higher composition laws. III: The parametrization of quartic rings
- Complexity of wild matrix problems and of isomorphism of algebras and graphs
- Complexity of matrix problems
- Higher composition laws. II: On cubic analogues of Gauss composition
- Higher composition laws. I: A new view on Gauss composition, and quadratic generalizations
- Efficient decomposition of associative algebras over finite fields
- General linear group action on tensors: a candidate for post-quantum cryptography
- Computational complexity of \(k\)-block conjugacy
- Polynomial-time algorithms for quadratic isomorphism of polynomials: the regular case
- Hilbert's Nullstellensatz is in the polynomial hierarchy
- Zero knowledge and circuit minimization
- Higher composition laws. IV: The parametrization of quintic rings
- Practical graph isomorphism. II.
- Complexity of ring morphism problems
- Metabelian groups and trilinear forms
- Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms
- On the automorphism groups of strongly regular graphs I
- Enumerating p -Groups. I: Inequalities
- Fast randomized algorithms for the structure of matrix algebras over finite fields (extended abstract)
- Undecidable problems: a sampler
- The asymptotic spectrum of tensors.
- Zero divisors in quaternion algebras
- Random Graph Isomorphism
- Is code equivalence easy to decide?
- Finding the permutation between equivalent linear codes: the support splitting algorithm
- Rough paths, Signatures and the modelling of functions on streams
- Learning Paths from Signature Tensors
- Algorithms Based on *-Algebras, and Their Applications to Isomorphism of Polynomials with One Secret, Group Isomorphism, and Polynomial Identity Testing
- FINITE QUASI-FROBENIUS MODULES AND LINEAR CODES
- MULTIPARTITE ENTANGLEMENT UNDER STOCHASTIC LOCAL OPERATIONS AND CLASSICAL COMMUNICATION
- Polynomial-time theory of matrix groups
- The threshold for subgroup profiles to agree is $\Omega(\log n)$
- Testing isomorphism of graded algebras
- Algorithms for Group Isomorphism via Group Extensions and Cohomology
- Graph isomorphism in quasipolynomial time [extended abstract]
- Computing isometry groups of Hermitian maps
- Deterministic Polynomial Time Algorithms for Matrix Completion Problems
- On the nlog n isomorphism technique (A Preliminary Report)
- Affine projections of polynomials
- Equivalence of $\mathbb{F}$ -Algebras and Cubic Forms
- STACS 2005
- Breaking the nlog n Barrier for Solvable-Group Isomorphism
- Non-Singular Multilinear Forms and Certain p-Way Matrix Factorizations
- Groups with Abelian Central Quotient Group
- On p-group isomorphism: search-to-decision, counting-to-decision, and nilpotency class reductions via tensors
This page was built for publication: On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness
