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 [ x 1 x 2 x n ] 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 \cite{GKL12} (STOC, 2012). Indeed, prior to our work, efficient reconstruction algorithms for multilinear ( k ) circuits were known only for the case of k = 2 \cite{GKL12, Volkovich17}.