Multilinear Complexity is Equivalent to Optimal Tester Size.
Nader H. Bshouty · Electronic colloquium on computational complexity · 2013
In this paper we first show that Tester for an F-algebra A and multilinear forms, [2], is equivalent to multilinear algorithm for the product of elements in A, [3]. Our result is constructive in deterministic polynomial time. We show that given a tester of size ν 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 ν and vise versa. This with the constructions in [2] 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 [11] for the product of d elements in A.