ECCC-Report TR13-011https://eccc.weizmann.ac.il/report/2013/011Comments and Revisions published for TR13-011en-usSun, 13 Jan 2013 09:51:19 +0200
Paper TR13-011
| Multilinear Complexity is Equivalent to Optimal Tester Size |
Nader Bshouty
https://eccc.weizmann.ac.il/report/2013/011In this paper we first show that Tester for an $F$-algebra $A$
and multilinear forms (see Testers and their Applications ECCC 2012) is equivalent to multilinear
algorithm for the product of elements in $A$
(see Algebraic
complexity theory. vol. 315, Springer-Verlag). Our
result is constructive in deterministic polynomial time. We show
that given a tester of size $\nu$ for an $F$-algebra $A$
and multilinear forms of degree $d$ one can in deterministic
polynomial time construct a multilinear algorithm for the
multiplication of $d$ elements of the algebra of multilinear
complexity $\nu$ and vise versa.
This with the constructions in above paper give the first polynomial
time construction of a bilinear algorithm with linear bilinear
complexity for the multiplication of two elements in any extension
finite field.
We then study the problem of simulating a substitution of an
assignment from an $F$-algebra $A$ in a degree $d$
multivariate polynomials with substitution of assignments from the
ground field $F$. We give a complete classification of all
algebras for which this can be done and show that this problem is
equivalent to constructing symmetric multilinear
algorithms for the product of $d$ elements in $A$.Sun, 13 Jan 2013 09:51:19 +0200https://eccc.weizmann.ac.il/report/2013/011