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 polynomials that can be written in the form $f(\bar{x}) =
\sum_{i=1}^{k} h_i(\bar{x}) \cdot g_i (\bar{x})$, where each $h_i$
is a polynomial that depends on only $\rho$ linear functions, and
each $g_i$ is a product of linear functions. Namely, we focus on polynomials computed by generalized depth-3 circuit with bounded top fan-in (when $h_i=1$, for
each $i$, then we get the class of depth-3 circuits with $k$
multiplication gates). We obtain the following results.

1. A quasi-polynomial time deterministic black-box identity testing algorithm for generalized depth-3 arithmetic circuits with top fan-in equal k.

2. A randomized black-box algorithm for identity testing of generalized depth-3 circuits with constant top fan-in, that uses a poly-logarithmic number of random bits, and makes a single query to the black-box.

3. A polynomial time deterministic black-box identity testing algorithm for read-k depth-3 circuits (each variable appears at most k times).

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 for depth-3 arithmetic circuits with top fan-in equal k. 2. A randomized black-box algorithm for identity testing of depth-3 circuits with constant top fan-in, that uses a poly-logarithmic number of random bits, and makes a single query to the black-box. 3. A polynomial time deterministic black-box identity testing algorithm for multilinear depth-3 circuits with constant top fan-in (each multiplication gate computes a multilinear polynomial).

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 for depth-3 arithmetic circuits with top fan-in equal k.

2. A randomized black-box algorithm for identity testing of
depth-3 circuits with constant top fan-in, that uses a poly-logarithmic number of random bits, and makes a single query to the black-box.

3. A polynomial time deterministic black-box identity testing algorithm
for multilinear depth-3 circuits with constant top fan-in (each multiplication gate computes a multilinear polynomial).

Comment This is a multi-part message in MIME format. ------=_NextPart_000_00C7_01C8641E.8206F670 Content-Type: multipart/alternative; boundary="----=_NextPart_001_00C8_01C8641E.82096770" ------=_NextPart_001_00C8_01C8641E.82096770 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Contact: zkarnin@cs.technion.ac.il Author: Zohar s. Karnin Title: Comment on: TR07-042

The paper in revision 01 is superseded by the ECCC Technical
Report TR07-042, revision 02.