When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.118
URN: urn:nbn:de:0030-drops-157143
URL: https://drops.dagstuhl.de/opus/volltexte/2022/15714/
 Go to the corresponding LIPIcs Volume Portal

### Efficient Reconstruction of Depth Three Arithmetic Circuits with Top Fan-In Two

 pdf-format:

### Abstract

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×(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 black-box 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 in-degree ≤ 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 in-degree two.
Prior to our work, black-box 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 quasi-polynomial in n,d,|𝔽| and that in [Karnin and Shpilka, 2009] is quasi-polynomial 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 Fan-In Two}},
booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages =	{118:1--118:33},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-217-4},
ISSN =	{1868-8969},
year =	{2022},
volume =	{215},
editor =	{Braverman, Mark},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},