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 \in \mathbb {F}[x_{1},x_{2},\ldots,x_{n} ] \) computable by a multilinear ΣΠΣΠ ( k ) circuit of size s , the algorithm runs in time quasi-poly( \(n,s,|\mathbb {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].