ECCC-Report TR07-042https://eccc.weizmann.ac.il/report/2007/042Comments and Revisions published for TR07-042en-usFri, 08 Feb 2008 07:02:03 +0200
Comment 1
| 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 |
https://eccc.weizmann.ac.il/report/2007/042#comment1
The paper in revision 01 is superseded by the ECCC Technical
Report TR07-042, revision 02.
Fri, 08 Feb 2008 07:02:03 +0200https://eccc.weizmann.ac.il/report/2007/042#comment1
Revision 2
| Author |
Zohar Karnin,
Amir Shpilka
https://eccc.weizmann.ac.il/report/2007/042#revision2In 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).
Thu, 31 Jan 2008 00:00:00 +0200https://eccc.weizmann.ac.il/report/2007/042#revision2
Revision 1
| Black Box Polynomial Identity Testing of Depth-3 Arithmetic Circuits with Bounded Top Fan-in |
Zohar Karnin,
Amir Shpilka
https://eccc.weizmann.ac.il/report/2007/042#revision1In 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).
Sun, 20 May 2007 00:00:00 +0300https://eccc.weizmann.ac.il/report/2007/042#revision1
Paper TR07-042
| Black Box Polynomial Identity Testing of Depth-3 Arithmetic Circuits with Bounded Top Fan-in |
Zohar Karnin,
Amir Shpilka
https://eccc.weizmann.ac.il/report/2007/042In 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).
Wed, 16 May 2007 10:46:11 +0300https://eccc.weizmann.ac.il/report/2007/042