Name
Abstract | ||
|---|---|---|
We present a randomized algorithm for reconstructing multilinear ΣΠΣΠ(2) circuits, i.e., multilinear depth-4 circuits with fan-in 2 at the top + gate. The algorithm is given blackbox access to a polynomial f ∈ F[x1,...,xn] computable by a multilinear ΣΠΣΠ(2) circuit of size s and outputs an equivalent multilinear ΣΠΣΠ(2) circuit, runs in time poly(n,s), and works over any field F. This is the first reconstruction result for any model of depth-4 arithmetic circuits. Prior to our work, reconstruction results for bounded depth circuits were known only for depth-2 arithmetic circuits (Klivans & Spielman, STOC 2001), ΣΠΣ(2) circuits (depth-3 arithmetic circuits with top fan-in 2) (Shpilka, STOC 2007), and ΣΠΣ(k) with k=O(1) (Karnin & Shpilka, CCC 2009). Moreover, the running times of these algorithms have a polynomial dependence on |F| and hence do not work for infinite fields such as Q. Our techniques are quite different from the previous ones for depth-3 reconstruction and rely on a polynomial operator introduced by Karnin et al. (STOC 2010) and Saraf & Volkovich (STOC 2011) for devising blackbox identity tests for multilinear ΣΠΣΠ(k) circuits. Some other ingredients of our algorithm include the classical multivariate blackbox factoring algorithm by Kaltofen & Trager (FOCS 1988) and an average-case algorithm for reconstructing ΣΠΣ(2) circuits by Kayal. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1145/2213977.2214035 | Electronic Colloquium on Computational Complexity (ECCC) |
Keywords | Field | DocType |
depth-3 arithmetic circuit,randomized algorithm,depth-4 multilinear circuit,blackbox identity test,depth-2 arithmetic circuit,top fan-in,average-case algorithm,reconstruction result,blackbox access,depth-3 reconstruction,equivalent multilinear,classical multivariate blackbox factoring | Arithmetic circuits,Randomized algorithm,Discrete mathematics,Combinatorics,Polynomial,Fan-in,Operator (computer programming),Electronic circuit,Multilinear map,Mathematics,Bounded function | Conference |
Volume | Citations | PageRank |
18 | 3 | 0.40 |
References | Authors | |
29 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ankit Gupta | 1 | 362 | 36.47 |
| Neeraj Kayal | 2 | 263 | 19.39 |
| Satyanarayana V. Lokam | 3 | 6 | 0.78 |