Reconstruction of depth-4 multilinear circuits with top fan-in 2
Ankit Gupta, Neeraj Kayal, Satya Lokam · 2012
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.