Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR07-042 | 31st January 2008 00:00

Author

RSS-Feed




Revision #2
Authors: Zohar Karnin, Amir Shpilka
Accepted on: 31st January 2008 00:00
Downloads: 3000
Keywords: 


Abstract:

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 to TR07-042 | 20th May 2007 00:00

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





Revision #1
Authors: Zohar Karnin, Amir Shpilka
Accepted on: 20th May 2007 00:00
Downloads: 3077
Keywords: 


Abstract:

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


Paper:

TR07-042 | 7th May 2007 00:00

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





TR07-042
Authors: Zohar Karnin, Amir Shpilka
Publication: 16th May 2007 10:46
Downloads: 3211
Keywords: 


Abstract:

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(s):

Comment #1 to TR07-042 | 8th February 2008 07:02

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





Comment #1
Authors:
Accepted on: 8th February 2008 07:02
Downloads: 1905
Keywords: 


Abstract:


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




ISSN 1433-8092 | Imprint