Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > MULTILINEAR:
Reports tagged with multilinear:
TR07-042 | 7th May 2007
Zohar Karnin, Amir Shpilka

Black Box Polynomial Identity Testing of Depth-3 Arithmetic Circuits with Bounded Top Fan-in

Revisions: 2 , Comments: 1

In this paper we consider the problem of determining whether an
unknown arithmetic circuit, for which we have oracle access,
computes the identically zero polynomial. Our focus is on depth-3
circuits with a bounded top fan-in. We obtain the following
results.

1. A quasi-polynomial time deterministic black-box identity testing algorithm ... more >>>




ISSN 1433-8092 | Imprint