Abstract
In this paper we develop efficient randomized algorithms to solve the blackbox 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 indegree two. Such circuits naturally compute polynomials of the form G×(T₁ + T₂), where G,T₁,T₂ are product of affine forms computed at the first layer in the circuit, and polynomials T₁,T₂ 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₁ and T₂. 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 blackbox access to a polynomial f (over finite field 𝔽), computable by such a circuit. Here are the results.
 [Low rank]: When 5 ≤ rank(f) = O(log³ d), it runs in time (nd^{log³d}log 𝔽)^{O(1)}, and, with high probability, outputs a depth three circuit computing f, with top addition gate having indegree ≤ d^{rank(f)}.
 [High rank]: When rank(f) = Ω(log³ d), it runs in time (ndlog 𝔽)^{O(1)}, and, with high probability, outputs a depth three circuit computing f, with top addition gate having indegree two.
Prior to our work, blackbox reconstruction for this circuit class was addressed in [Amir Shpilka, 2007; Karnin and Shpilka, 2009; Sinha, 2016]. Reconstruction algorithm in [Amir Shpilka, 2007] runs in time quasipolynomial in n,d,𝔽 and that in [Karnin and Shpilka, 2009] is quasipolynomial in d,𝔽. Algorithm in [Sinha, 2016] 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 𝔽. This problem has been mentioned as an open problem in [Ankit Gupta et al., 2012] (STOC 2012). In the high rank case, our algorithm runs in (ndlog𝔽)^{O(1)} time, thereby significantly improving the existing algorithms in [Amir Shpilka, 2007; Karnin and Shpilka, 2009].
BibTeX  Entry
@InProceedings{sinha:LIPIcs.ITCS.2022.118,
author = {Sinha, Gaurav},
title = {{Efficient Reconstruction of Depth Three Arithmetic Circuits with Top FanIn Two}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {118:1118:33},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772174},
ISSN = {18688969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15714},
URN = {urn:nbn:de:0030drops157143},
doi = {10.4230/LIPIcs.ITCS.2022.118},
annote = {Keywords: Arithmetic Circuits, Circuit Reconstruction}
}
Keywords: 

Arithmetic Circuits, Circuit Reconstruction 
Collection: 

13th Innovations in Theoretical Computer Science Conference (ITCS 2022) 
Issue Date: 

2022 
Date of publication: 

25.01.2022 