论文标题
确定性和跟踪IMM等效测试之间的随机多项式时间当量
Randomized polynomial-time equivalence between determinant and trace-IMM equivalence tests
论文作者
论文摘要
多项式家族{g_m}在字段f上进行的等效测试是以下问题：给定的黑框访问n变量多项式f（x），其中n是g_m中的变量的数量，检查是否存在GL（n，f）中的a a a a a in a in gl（n，f），例如f（x）= g_m（ax）。如果是的，则输出这样的A。已经研究了许多重要多项式家族的等效测试的复杂性，包括行列式（DET）和迭代矩阵乘法的两个流行变体多项式：IMM_ {w，d，d}（w，d，d}（（1,1）（（1,1），d $ \ times $ w符号$ w符号的dms和trims）和trims trim yms ym s trims and trime trims yms yms yms ym ex and trims ym ex s yms ym ex and trims ym ex and（w s srtroc）。 d多W $ \ times $ w象征矩阵的产物。家族DET，IMM和TR-IMM是VBP完整的，因此，从这个意义上讲，它们具有相同的复杂性。但是，它们是否具有相同的等效测试复杂性？我们证明答案是det和tr-imm的“是”（模仿随机性的使用）。结果是通过通过另一个研究的问题（称为完整矩阵代数同构问题（FMAI））连接两个问题来获得的结果。特别是，我们证明了以下内容： 1。多项式与Tr-imm_ {W，d}的测试等效性，对于D $ \ geq $ 3和W $ \ geq $ 2，是随机的多项式时间Turing，可降低到det_w的测试等效性与det_w的等值降低，是w $ \ w $ \ w $ \ w $ w $ w $ w matrix的正式变量的决定性。 （在这里，d不必是一个常数。） 2。FMAI是对等效性测试（实际上是张张异构测试）的随机多项式图，用于矩阵乘法张量{tr-imm_ {w，3}}的家族。 这些结合了从确定性等效性测试到FMAI的随机多时间降低的结合。
Equivalence testing for a polynomial family {g_m} over a field F is the following problem: Given black-box access to an n-variate polynomial f(x), where n is the number of variables in g_m, check if there exists an A in GL(n,F) such that f(x) = g_m(Ax). If yes, then output such an A. The complexity of equivalence testing has been studied for a number of important polynomial families, including the determinant (Det) and the two popular variants of the iterated matrix multiplication polynomial: IMM_{w,d} (the (1,1) entry of the product of d many w $\times$ w symbolic matrices) and Tr-IMM_{w,d} (the trace of the product of d many w $\times$ w symbolic matrices). The families Det, IMM and Tr-IMM are VBP-complete, and so, in this sense, they have the same complexity. But, do they have the same equivalence testing complexity? We show that the answer is 'yes' for Det and Tr-IMM (modulo the use of randomness). The result is obtained by connecting the two problems via another well-studied problem called the full matrix algebra isomorphism problem (FMAI). In particular, we prove the following: 1. Testing equivalence of polynomials to Tr-IMM_{w,d}, for d$\geq$ 3 and w$\geq$ 2, is randomized polynomial-time Turing reducible to testing equivalence of polynomials to Det_w, the determinant of the w $\times$ w matrix of formal variables. (Here, d need not be a constant.) 2. FMAI is randomized polynomial-time Turing reducible to equivalence testing (in fact, to tensor isomorphism testing) for the family of matrix multiplication tensors {Tr-IMM_{w,3}}. These in conjunction with the randomized poly-time reduction from determinant equivalence testing to FMAI [Garg,Gupta,Kayal,Saha19], imply that FMAI, equivalence testing for Tr-IMM and for Det, and the $3$-tensor isomorphism problem for the family of matrix multiplication tensors are randomized poly-time equivalent under Turing reductions.
