Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Grochow, Joshua A.; Qiao, Youming; Tang, Gang https://www.dagstuhl.de/lipics License: Creative Commons Attribution 4.0 license (CC BY 4.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-136836
URL:

; ;

Average-Case Algorithms for Testing Isomorphism of Polynomials, Algebras, and Multilinear Forms

pdf-format:


Abstract

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 ∈ 𝔽_q[x_1, … , 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.

BibTeX - Entry

@InProceedings{grochow_et_al:LIPIcs.STACS.2021.38,
  author =	{Grochow, Joshua A. and Qiao, Youming and Tang, Gang},
  title =	{{Average-Case Algorithms for Testing Isomorphism of Polynomials, Algebras, and Multilinear Forms}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{38:1--38:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13683},
  URN =		{urn:nbn:de:0030-drops-136836},
  doi =		{10.4230/LIPIcs.STACS.2021.38},
  annote =	{Keywords: polynomial isomorphism, trilinear form equivalence, algebra isomorphism, average-case algorithms, tensor isomorphism complete, symmetric and alternating bilinear maps}
}

Keywords: polynomial isomorphism, trilinear form equivalence, algebra isomorphism, average-case algorithms, tensor isomorphism complete, symmetric and alternating bilinear maps
Seminar: 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Issue date: 2021
Date of publication: 10.03.2021


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI