Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR19-104 | 6th August 2019 23:16

Reconstruction of Depth-$4$ Multilinear Circuits

RSS-Feed




TR19-104
Authors: Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
Publication: 11th August 2019 07:14
Downloads: 1181
Keywords: 


Abstract:

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}.



ISSN 1433-8092 | Imprint