Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR20-125 | 17th August 2020 19:32

Efficient reconstruction of depth three circuits with top fan-in two


Authors: Gaurav Sinha
Publication: 17th August 2020 22:11
Downloads: 90


In this paper we develop efficient randomized algorithms to solve the black-box reconstruction problem for polynomials(over finite fields) computable by depth three arithmetic circuits with alternating addition/multiplication gates, such that top(output) gate is an addition gate with in-degree $2$. Such circuits naturally compute polynomials of the form $G\times(T_1 + T_2)$, where $G,T_1,T_2$ are product of affine forms computed at the first(addition) layer in the circuit, and polynomials $T_1,T_2$ have no common factors. Rank of such a circuit is defined to be the dimension of vector space spanned by all affine factors of $T_1$ and $T_2$. For any polynomial $f$ computable by such a circuit, $rank(f)$ is defined to be the minimum rank of any such circuit computing it. Our work develops randomized algorithms, which take as input a black-box computing polynomial $f$, with coefficients in a finite field $\mathbb{F}$, exhibiting such a circuit. Here are the results.

$[$Low rank$]:$ When $5\leq r = rank(f) = O(\log^3 d)$, it runs in time $(nd^{\log^3d}\log |\mathbb{F}|)^{O(1)}$ and outputs a depth three circuit computing $f$ (with high probability), with top addition gate having in-degree $\leq d^{rank(f)}$.

$[$High rank$]:$ When $rank(f) = \Omega(\log^3 d)$, it runs in time $(nd\log |\mathbb{F}|)^{O(1)}$, and with high probability outputs a depth three circuit computing $f$, with top addition gate having in-degree $2$.

Prior to our work, black-box reconstruction for this circuit class was addressed in [Shp07, KS09, Sin16b]. Reconstruction algorithm in [Shp07] runs in time quasi-polynomial in $n,d,|\mathbb{F}|$ and that in [KS09] is quasi-polynomial in $d,|\mathbb{F}|$. Algorithm in [Sin16b] works only for polynomials over characteristic zero fields. Thus ours is the first blackbox reconstruction algorithm for this class of circuits that runs in time polynomial in $\log |\mathbb{F}|$. This problem has been mentioned as an open problem in [GKL12] (STOC 2012). In the high rank case, our algorithm runs in $(nd\log|\mathbb{F}|)^{O(1)}$ time, thereby significantly improving the existing algorithms in [Shp07, KS09].

ISSN 1433-8092 | Imprint