__
TR13-011 | 10th January 2013 09:42
__

#### Multilinear Complexity is Equivalent to Optimal Tester Size

**Abstract:**
In 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$.