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

We study the problems of testing isomorphism of polynomials, algebras, andmultilinear forms. Our first main results are average-case algorithms for theseproblems. 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$ areisomorphic in time $q^{O(n)}$ for most $f$. This average-case setting hasdirect practical implications, having been studied in multivariate cryptographysince the 1990s. Our second result concerns the complexity of testingequivalence of alternating trilinear forms. This problem is of interest in bothmathematics and cryptography. We show that this problem is polynomial-timeequivalent to testing equivalence of symmetric trilinear forms, by showing thatthey are both Tensor Isomorphism-complete (Grochow-Qiao, ITCS, 2021), thereforeis equivalent to testing isomorphism of cubic forms over most fields.Comment: Journal version at the journal of Groups, Complexity, Cryptolog