Joshua A. Grochow ; Youming Qiao ; Gang Tang - Average-case algorithms for testing isomorphism of polynomials, algebras, and multilinear forms

gcc:9431 - journal of Groups, complexity, cryptology, August 11, 2022, Volume 14, Issue 1 - https://doi.org/10.46298/jgcc.2022.14.1.9431
Average-case algorithms for testing isomorphism of polynomials, algebras, and multilinear formsArticle

Authors: Joshua A. Grochow ; Youming Qiao ; Gang Tang

    We study the problems of testing isomorphism of polynomials, algebras, and multilinear forms. Our first main results are average-case algorithms for these problems. For example, we develop an algorithm that takes two cubic forms $f, g\in \mathbb{F}_q[x_1,\dots, x_n]$, and decides whether $f$ and $g$ are isomorphic in time $q^{O(n)}$ for most $f$. This average-case setting has direct practical implications, having been studied in multivariate cryptography since the 1990s. Our second result concerns the complexity of testing equivalence of alternating trilinear forms. This problem is of interest in both mathematics and cryptography. We show that this problem is polynomial-time equivalent to testing equivalence of symmetric trilinear forms, by showing that they are both Tensor Isomorphism-complete (Grochow-Qiao, ITCS, 2021), therefore is equivalent to testing isomorphism of cubic forms over most fields.


    Volume: Volume 14, Issue 1
    Published on: August 11, 2022
    Accepted on: August 1, 2022
    Submitted on: May 6, 2022
    Keywords: Computer Science - Data Structures and Algorithms,Computer Science - Computational Complexity
    Funding:
      Source : OpenAIRE Graph
    • Collaborative Research: New Algorithms for Group Isomorphism; Funder: National Science Foundation; Code: 1750319
    • Discovery Projects - Grant ID: DP160101652; Funder: Australian Research Council (ARC); Code: DP160101652
    • Discovery Projects - Grant ID: DP200100950; Funder: Australian Research Council (ARC); Code: DP200100950

    2 Documents citing this article

    Consultation statistics

    This page has been seen 1332 times.
    This article's PDF has been downloaded 416 times.