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

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > BILINEAR ALGORITHMS:
Reports tagged with Bilinear algorithms:
TR13-011 | 10th January 2013
Nader Bshouty

Multilinear Complexity is Equivalent to Optimal Tester Size

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. ... more >>>




ISSN 1433-8092 | Imprint