| Field |
Value |
Language |
|
dc.contributor.author |
Tang, G |
|
|
dc.contributor.author |
Qiao, Y
https://orcid.org/0000-0003-4334-1449
|
|
|
dc.contributor.author |
Grochow, JA |
|
|
dc.date.accessioned |
2023-02-15T01:25:01Z |
|
|
dc.date.available |
2023-02-15T01:25:01Z |
|
|
dc.date.issued |
2022-08-11 |
|
|
dc.identifier.citation |
Groups – Complexity – Cryptology, 2022, Volume 14, Issue 1 |
|
|
dc.identifier.issn |
1867-1144 |
|
|
dc.identifier.issn |
1869-6104 |
|
|
dc.identifier.uri |
http://hdl.handle.net/10453/166128
|
|
|
dc.description.abstract |
<jats:p>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.</jats:p> |
|
|
dc.language |
en |
|
|
dc.publisher |
Centre pour la Communication Scientifique Directe (CCSD) |
|
|
dc.relation.ispartof |
Groups – Complexity – Cryptology |
|
|
dc.relation.isbasedon |
10.46298/jgcc.2022.14.1.9431 |
|
|
dc.rights |
info:eu-repo/semantics/openAccess |
|
|
dc.subject |
08 Information and Computing Sciences |
|
|
dc.title |
Average-case algorithms for testing isomorphism of polynomials, algebras, and multilinear forms |
|
|
dc.type |
Journal Article |
|
|
utslib.citation.volume |
Volume 14, Issue 1 |
|
|
utslib.for |
08 Information and Computing Sciences |
|
|
pubs.organisational-group |
/University of Technology Sydney |
|
|
pubs.organisational-group |
/University of Technology Sydney/Faculty of Engineering and Information Technology |
|
|
pubs.organisational-group |
/University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information |
|
|
pubs.organisational-group |
/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science |
|
|
utslib.copyright.status |
open_access |
* |
|
dc.date.updated |
2023-02-15T01:25:00Z |
|
|
pubs.publication-status |
Published online |
|
|
pubs.volume |
Volume 14, Issue 1 |
|
