A Caltech Library Service

Blackbox Reconstruction of Depth Three Circuits with Top Fan-In Two


Sinha, Gaurav (2016) Blackbox Reconstruction of Depth Three Circuits with Top Fan-In Two. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/Z92N507D.


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 thesis we present a polynomial time randomized algorithm for reconstructing ΣΠΣ(2) circuits over characteristic zero fields F i.e. depth−3 circuits with fan-in 2 at the top addition gate and having coefficients from a field of characteristic zero.

The algorithm needs only a black-box query access to the polynomial f ∈ F[x1,...,xn] 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 g.c.d. of the two multiplication gates) is bigger than a fixed constant. Our algorithm runs in time polynomial in n and d and with high probability returns an equivalent ΣΠΣ(2) circuit.

The problem of reconstructing ΣΠΣ(2) circuits over finite fields was first proposed by Shpilka [27]. The generalization to ΣΠΣ(k) circuits, k = O(1) (over finite fields) was addressed by Karnin and Shpilka in [18]. 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 setting, such ideas immediately pose a problem and we need new techniques.

Our main techniques are based on the use of quantitative Sylvester Gallai theorems from the work of Barak [3] to find a small collection of "nice" subspaces to project onto. The heart of this work 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 [9] 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 [17].

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:Reconstruction, Interpolation, Arithmetic circuits, Black-box
Degree Grantor:California Institute of Technology
Division:Physics, Mathematics and Astronomy
Major Option:Mathematics
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Rains, Eric M.
Thesis Committee:
  • Rains, Eric M. (chair)
  • Schulman, Leonard J.
  • Umans, Christopher M.
  • Katz, Nets H.
Defense Date:25 May 2016
Non-Caltech Author Email:sinhagaur88 (AT)
Record Number:CaltechTHESIS:06082016-032155301
Persistent URL:
Related URLs:
URLURL TypeDescription Paper: "Reconstruction of Real Depth-3 Circuits with Top Fan-In 2”. In: 31st Conference on Computational Complexity (CCC 2016)
Sinha, Gaurav0000-0002-3590-9543
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:9861
Deposited By: Gaurav Sinha
Deposited On:22 Jun 2016 17:55
Last Modified:04 Oct 2019 00:14

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page