Sinha, Gaurav
Reconstruction of Real Depth3 Circuits with Top FanIn 2
Abstract
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 SigmaPiSigma(2) circuits over F (char(F)=0), i.e. depth3 circuits with fanin 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 in F[x_1,..., x_n] of degree d, computable by a SigmaPiSigma(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 SigmaPiSigma(2) circuit (with high probability).
The problem of reconstructing SigmaPiSigma(2) circuits over finite fields was first proposed by Shpilka [Shpilka, STOC 2007]. The generalization to SigmaPiSigma(k) circuits, k = O(1) (over finite fields) was addressed by Karnin and Shpilka in [Karnin/Shpilka, CCC 2015]. 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. [Barak/Dvir/Wigderson/Yehudayoff, STOC 2011] 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 [Gelfand/Kapranov/Zelevinsky, 1994] 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 [Kaltofen/Trager, J. Symb. Comp. 1990].
BibTeX  Entry
@InProceedings{sinha:LIPIcs:2016:5854,
author = {Gaurav Sinha},
title = {{Reconstruction of Real Depth3 Circuits with Top FanIn 2}},
booktitle = {31st Conference on Computational Complexity (CCC 2016)},
pages = {31:131:53},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770088},
ISSN = {18688969},
year = {2016},
volume = {50},
editor = {Ran Raz},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5854},
URN = {urn:nbn:de:0030drops58545},
doi = {10.4230/LIPIcs.CCC.2016.31},
annote = {Keywords: Reconstruction, SigmaPiSigma(2), SylvesterGallai, Brill's Equations}
}
19.05.2016
Keywords: 

Reconstruction, SigmaPiSigma(2), SylvesterGallai, Brill's Equations 
Seminar: 

31st Conference on Computational Complexity (CCC 2016)

Issue date: 

2016 
Date of publication: 

19.05.2016 