Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR13-011 | 10th January 2013 09:42

Multilinear Complexity is Equivalent to Optimal Tester Size

RSS-Feed




TR13-011
Authors: Nader Bshouty
Publication: 13th January 2013 09:51
Downloads: 2952
Keywords: 


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.



ISSN 1433-8092 | Imprint