Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR19-104 | 6th August 2019 23:16

#### Reconstruction of Depth-$4$ Multilinear Circuits

TR19-104
Authors: Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
Publication: 11th August 2019 07:14
We present a deterministic algorithm for reconstructing multilinear $\Sigma\Pi\Sigma\Pi(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 $\Sigma\Pi\Sigma\Pi(k)$ circuit of size $s$, the algorithm runs in time quasi-poly($n,s,{|\mathbb{F}|}$) and outputs a multilinear $\Sigma\Pi\Sigma\Pi(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 $\Sigma\Pi\Sigma\Pi(k)$ circuits were known only for the case of $k=2$ \cite{GKL12, Volkovich17}.