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

Reorganized introduction, Presented key ideas for proposition 1 and 2 in introduction, corrected typos

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 output gate is an addition gate with in-degree two. 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 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 reconstruction algorithms which take as input black-box access to a polynomial $f$ (over finite field $\mathbb{F}$), computable by such a circuit. Here are the results.

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

Prior to our work, black-box reconstruction for this circuit class was addressed in \cite{Shp07, Karnin2009, Sinha2016}. Reconstruction algorithm in \cite{Shp07} runs in time quasi-polynomial in $n,d,|\mathbb{F}|$ and that in \cite{Karnin2009} is quasi-polynomial in $d,|\mathbb{F}|$. Algorithm in \cite{Sinha2016} 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 \cite{Gupta2012} (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 \cite{Shp07, Karnin2009}.

Better organization. Added some missing proofs. Re-wrote some proofs/sections for better presentation.

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