Revision #2 Authors: Zohar Karnin, Amir Shpilka

Accepted on: 31st January 2008 00:00

Downloads: 2818

Keywords:

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

Revision #1 Authors: Zohar Karnin, Amir Shpilka

Accepted on: 20th May 2007 00:00

Downloads: 2872

Keywords:

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

TR07-042 Authors: Zohar Karnin, Amir Shpilka

Publication: 16th May 2007 10:46

Downloads: 2952

Keywords:

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

The paper in revision 01 is superseded by the ECCC Technical

Report TR07-042, revision 02.