Reconstruction of Depth-4 Multilinear Circuits

We present a deterministic algorithm for reconstructing multilinear ΣΠΣΠ() circuits, i.e. multilinear depth-4 circuits with fan-in at the top + gate. For any ixed , given black-box access to a polynomial ∈ F[ 1 , 2 , . . . , ] computable by a multilinear ΣΠΣΠ() circuit of size , the algorithm runs in time quasi-poly(, , |F|) and outputs a multilinear ΣΠΣΠ() circuit of size quasi-poly(, ) that computes .

Our result solves an open problem posed in [GKL12] (STOC, 2012). Indeed, prior to our work, eicient reconstruction algorithms for multilinear ΣΠΣΠ() circuits were known only for the case of = 2 [GKL12,Vol17].

CCS Concepts: • Theory of computation → Algebraic complexity theory; Design and analysis of algorithms.