Reconstruction of Depth-4 Multilinear Circuits

We present a deterministic algorithm for reconstructing multilinear ΣΠΣΠ(k) circuits, i.e. multilinear depth-4 circuits with fan-in k at the top + gate. For any fixed k, given black-box access to a polynomial f∈F[x1,x2,…,xn] computable by a multilinear ΣΠΣΠ(k) circuit of size s, the algorithm runs in time quasi-poly(n,s,|F|) and outputs a multilinear ΣΠΣΠ(k) circuit of size quasi-poly(n, s) that computes f. Our result solves an open problem posed in [GKL12] (STOC, 2012). Indeed, prior to our work, efficient reconstruction algorithms for multilinear ΣΠΣΠ(k) circuits were known only for the case of k = 2 [GKL12,Vol17].