Average-case algorithms for testing isomorphism of polynomials, algebras, and multilinear forms

DOI10.46298/JGCC.2022.14.1.9431MaRDI QIDQ6566798zbMATH OpenFDO

Authors Joshua A. Grochow, Youming Qiao, Gang Tang

Publication date 3 July 2024

Published in Journal of Groups, Complexity, Cryptology (Search for Journal in Brave)

Copyright license arXiv.org Non-exclusive license to distribute

Full work available at URL https://doi.org/10.46298/JGCC.2022.14.1.9431

zbMATH Keywords

algebra isomorphismcompletenesspolynomial isomorphismtensor isomorphism

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Recommendations

• Polynomial-time algorithms for quadratic isomorphism of polynomials: the regular case
• Graph-theoretic algorithms for the ``isomorphism of polynomials problem
• Algorithms based on \(*\)-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing
• Algorithms based on -algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing
• scientific article; zbMATH DE number 1303122

Cites work

• Algorithms based on \(*\)-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing
• Computing isometry groups of Hermitian maps
• Decomposing \(p\)-groups via Jordan algebras.
• Efficient algorithms for some special cases of the polynomial equivalence problem
• Equivalence of $\mathbb{F}$ -Algebras and Cubic Forms
• Hidden fields equations (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms
• scientific article; zbMATH DE number 475362 (Why is no real title available?)
• scientific article; zbMATH DE number 1950436 (Why is no real title available?)
• Improved Algorithms for Alternating Matrix Space Isometry: From Theory to Practice
• On p-group isomorphism: search-to-decision, counting-to-decision, and nilpotency class reductions via tensors
• Polynomial-time algorithms for quadratic isomorphism of polynomials: the regular case
• Practical cryptanalysis of the identification scheme based on the isomorphism of polynomial with one secret problem
• Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
• STACS 2005
• Testing shift-equivalence of polynomials by deterministic, probabilistic and quantum machines.
• Wildness for tensors

Cited in

(7)

• On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness
• Graph-theoretic algorithms for the alternating trilinear form equivalence problem
• Algebraic algorithm for the alternating trilinear form equivalence problem
• Algorithms for matrix code and alternating trilinear form equivalences via new isomorphism invariants
• On the complexity of isomorphism problems for tensors, groups, and polynomials III: actions by classical groups
• Rare structures in tensor graphs. Bermuda triangles for cryptosystems based on the tensor isomorphism problem
• Reducing signature size of matrix-code-based signature schemes

This page was built for publication: Average-case algorithms for testing isomorphism of polynomials, algebras, and multilinear forms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6566798)