A Caltech Library Service

Reconstruction of real depth-3 circuits with top fan-in 2

Sinha, Gaurav (2016) Reconstruction of real depth-3 circuits with top fan-in 2. In: 31st Conference on Computational Complexity (CCC'16). Leibniz International Proceedings in Informatics. No.50. Dagstuhl Publishing , Wadern, Germany, Art. No. 31. ISBN 978-3-95977-008-8.

[img] PDF - Published Version
Creative Commons Attribution.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Reconstruction of arithmetic circuits has been heavily studied in the past few years and has connections to proving lower bounds and deterministic identity testing. In this paper we present a polynomial time randomized algorithm for reconstructing ΣΠΣ(2) circuits over F (char(F) = 0), i.e. depth-3 circuits with fan-in 2 at the top addition gate and having coefficients from a field of characteristic 0. The algorithm needs only a blackbox query access to the polynomial f ∈ F[x_1, ..., x_n] of degree d, computable by a ΣΠΣ(2) circuit C. In addition, we assume that the "simple rank" of this polynomial (essential number of variables after removing the gcd of the two multiplication gates) is bigger than a fixed constant. Our algorithm runs in time poly(n, d) and returns an equivalent ΣΠΣ(2) circuit (with high probability). The problem of reconstructing ΣΠΣ(2) circuits over finite fields was first proposed by Shpilka [24]. The generalization to ΣΠΣ(k) circuits, k = O(1) (over finite fields) was addressed by Karnin and Shpilka in [15]. The techniques in these previous involve iterating over all objects of certain kinds over the ambient field and thus the running time depends on the size of the field F. Their reconstruction algorithm uses lower bounds on the lengths of Linear Locally Decodable Codes with 2 queries. In our settings, such ideas immediately pose a problem and we need new ideas to handle the case of the characteristic 0 field F. Our main techniques are based on the use of Quantitative Sylvester Gallai Theorems from the work of Barak et al. [3] to find a small collection of "nice" subspaces to project onto. The heart of our paper lies in subtle applications of the Quantitative Sylvester Gallai theorems to prove why projections w.r.t. the "nice" subspaces can be "glued". We also use Brill's Equations from [8] to construct a small set of candidate linear forms (containing linear forms from both gates). Another important technique which comes very handy is the polynomial time randomized algorithm for factoring multivariate polynomials given by Kaltofen [14].

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Alternate Title:Reconstruction of depth-3, top fan-in two circuits over characteristic zero fields
Additional Information:© 2016 Gaurav Sinha; licensed under Creative Commons License CC-BY. I am extremely thankful to Neeraj Kayal for introducing me to this problem. Sukhada Fadnavis, Neeraj Kayal and myself started working on the problem together during my summer internship at Microsoft Research India Labs in 2011. We solved the first important case together. I’m grateful to them for all helpful discussions, constant guidance and encouragement. I would like to thank Zeev Dvir for communicating the most recent rank bounds on δ − SGk configurations from [6] and his feedback on the work. This reduces the gap in the first problem we mentioned above. I would also like to thank Vinamra Agrawal, Pravesh Kothari and Piyush Srivastava for helpful discussions. I would also like to thank the anonymous reviewers for their suggestions. Lastly I would like to thank Microsoft Research for giving me the opportunity to intern at their Bangalore Labs with the Applied Mathematics Group.
Subject Keywords:Reconstruction, ΣΠΣ(2), Sylvester-Gallai, Brill’s Equations
Series Name:Leibniz International Proceedings in Informatics
Issue or Number:50
Classification Code:1998 ACM Subject Classification G.1.1 Interpolation, I.4.5 Reconstruction
Record Number:CaltechAUTHORS:20180807-140639799
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:88634
Deposited By: Tony Diaz
Deposited On:07 Aug 2018 21:24
Last Modified:03 Oct 2019 20:08

Repository Staff Only: item control page