Average-case algorithms for testing isomorphism of polynomials, Algebras, and multilinear forms
- Publication Type:
- Conference Proceeding
- Citation:
- Leibniz International Proceedings in Informatics, LIPIcs, 2021, 187
- Issue Date:
- 2021-03-01
Open Access
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is open access.
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 ∈ Fq [x1,...,xn], and decides whether f and g are isomorphic in time qO(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 Isomorphismcomplete (Grochow & Qiao, ITCS 2021), therefore is equivalent to testing isomorphism of cubic forms over most fields.
Please use this identifier to cite or link to this item: