Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #3 to TR15-150 | 26th November 2015 06:57

Reconstruction of Real depth-3 Circuits with top fan-in 2

RSS-Feed




Revision #3
Authors: Gaurav Sinha
Accepted on: 26th November 2015 06:57
Downloads: 954
Keywords: 


Abstract:

Reconstruction of arithmertic 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 $\Sigma\Pi\Sigma(2)$ circuits over $\R$, i.e. depth$-3$ circuits with fan-in $2$ at the top addition gate and having real coefficients.

The algorithm needs only a blockbox query access to the polynomial $f \in \R[x_1,\ldots, x_n]$ of degree $d$, computable by a $\Sigma\Pi\Sigma(2)$ circuit $C$. In addition, we assume that the \emph{"simple rank"} of this polynomial (essential number of variables after removing the gcd of the two multiplication gates) is bigger than a fixed constant $r$. Our algorithm runs in time $poly(n, d)$ and returns an equivalent $\Sigma\Pi\Sigma(2)$ circuit(with high probability).

The problem of reconstructing $\Sigma\Pi\Sigma(2)$ circuits over finite fields was first proposed by Shpilka \cite{Shpilka07}. The generalization to $\Sigma\Pi\Sigma(k)$ circuits, $k = O(1)$ (over finite fields) was addressed by Karnin and Shpilka in \cite{KarShp09}. 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 field \mathbb{R}.

Our main techniques are based on the use of Quantitative Syslvester Gallai Theorems from the work of Barak et.al. \cite{BDWY11} to find a small collection of \emph{"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 \emph{"nice"} subspaces can be ”glued”. We also use Brill's Equations from \cite{GKZ94} 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 \cite{KalTr90}.



Changes to previous version:

Added Sections to explain algorithms;
Rewrote and cleaned up parts of algorithms;
Corrected Typos


Revision #2 to TR15-150 | 17th September 2015 02:16

Reconstruction of $\Sigma\Pi\Sigma(2)$ Circuits over Reals





Revision #2
Authors: Gaurav Sinha
Accepted on: 17th September 2015 02:16
Downloads: 927
Keywords: 


Abstract:

Reconstruction of arithmertic 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 $\Sigma\Pi\Sigma(2)$ circuits over $\R$, i.e. depth$-3$ circuits with fan-in $2$ at the top addition gate and having real coefficients.

The algorithm needs only a blockbox query access to the polynomial $f \in \R[x_1,\ldots, x_n]$ of degree $d$, computable by a $\Sigma\Pi\Sigma(2)$ circuit $C$. In addition, we assume that the \emph{"simple rank"} of this polynomial (essential number of variables after removing the gcd of the two multiplication gates) is bigger than a fixed constant $r$. Our algorithm runs in time $poly(n, d)$ and returns an equivalent $\Sigma\Pi\Sigma(2)$ circuit(with high probability).

The problem of reconstructing $\Sigma\Pi\Sigma(2)$ circuits over finite fields was first proposed by Shpilka \cite{Shpilka07}. The generalization to $\Sigma\Pi\Sigma(k)$ circuits, $k = O(1)$ (over finite fields) was addressed by Karnin and Shpilka in \cite{KarShp09}. 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 real fields.

Our main techniques are based on the use of Quantitative Syslvester Gallai Theorems from the work of Barak et.al. \cite{BDWY11} to find a small collection of \emph{"nice"} subspaces to iterate over. The heart of our paper lies in subtle applications of the Quantitative Sylvester Gallai theorems to prove why projections w.r.t. the \emph{"nice"} subspaces can be ”glued”. We also use Brill's Equations from \cite{GKZ94} 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 \cite{KalTr90}.



Changes to previous version:

1. Updated rank bound for identically zero \Sigma\Pi\Sigma(k) circuits in Theorem 1.6 to the most
recent bounds given in [SS10].

2. Updated rank bound for $\delta-SG_k$ configurations
in Theorem 2.11 according to the improvement by Dvir et. al. in [DSW12]


Revision #1 to TR15-150 | 14th September 2015 19:43

Reconstruction of $\Sigma\Pi\Sigma(2)$ Circuits over Reals





Revision #1
Authors: Gaurav Sinha
Accepted on: 14th September 2015 19:43
Downloads: 877
Keywords: 


Abstract:

Reconstruction of arithmertic 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 $\Sigma\Pi\Sigma(2)$ circuits over $\R$, i.e. depth$-3$ circuits with fan-in $2$ at the top addition gate and having real coefficients.

The algorithm needs only a blackbox query access to the polynomial $f \in \R[x_1,\ldots, x_n]$ of degree $d$, computable by a $\Sigma\Pi\Sigma(2)$ circuit $C$. In addition, we assume that the \emph{"simple rank"} of this polynomial (essential number of variables after removing the gcd of the two multiplication gates) is bigger than a fixed constant $r$. Our algorithm runs in time $poly(n, d)$ and returns an equivalent $\Sigma\Pi\Sigma(2)$ circuit(with high probability).

The problem of reconstructing $\Sigma\Pi\Sigma(2)$ circuits over finite fields was first proposed by Shpilka \cite{Shpilka07}. The generalization to $\Sigma\Pi\Sigma(k)$ circuits, $k = O(1)$ (over finite fields) was addressed by Karnin and Shpilka in \cite{KarShp09}. 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 real fields.

Our main techniques are based on the use of Quantitative Syslvester Gallai Theorems from the work of Barak et.al. \cite{BDWY11} to find a small collection of \emph{"nice"} subspaces to iterate over. The heart of our paper lies in subtle applications of the Quantitative Sylvester Gallai theorems to prove why projections w.r.t. the \emph{"nice"} subspaces can be ”glued”. We also use Brill's Equations from \cite{GKZ94} 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 \cite{KalTr90}.



Changes to previous version:

Fixed typos in:
1. Abstract
2. Algorithm 7 and it's correctness on pg 31,32.


Paper:

TR15-150 | 13th September 2015 21:12

Reconstruction of $\Sigma\Pi\Sigma(2)$ Circuits over Reals





TR15-150
Authors: Gaurav Sinha
Publication: 14th September 2015 00:00
Downloads: 1103
Keywords: 


Abstract:

Reconstruction of arithmertic 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 $\Sigma\Pi\Sigma(2)$ circuits over $\R$, i.e. depth$-3$ circuits with fan-in $2$ at the top addition gate and having real coefficients.

The algorithm needs only a blockbox query access to the polynomial $f \in \R[x_1,\ldots, x_n]$ of degree $d$, computable by a $\Sigma\Pi\Sigma(2)$ circuit $C$. In addition, we assume that the \emph{"simple rank"} of this polynomial (essential number of variables after removing the gcd of the two multiplication gates) is bigger than a fixed constant $r$. Our algorithm runs in time $poly(n, d)$ and returns an equivalent $\Sigma\Pi\Sigma(2)$ circuit(with high probability).

The problem of reconstructing $\Sigma\Pi\Sigma(2)$ circuits over finite fields was first proposed by Shpilka \cite{Shpilka07}. The generalization to $\Sigma\Pi\Sigma(k)$ circuits, $k = O(1)$ (over finite fields) was addressed by Karnin and Shpilka in \cite{KarShp09}. 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 real fields.

Our main techniques are based on the use of Quantitative Syslvester Gallai Theorems from the work of Barak et.al. \cite{BDWY11} to find a small collection of \emph{"nice"} subspaces to iterate over. The heart of our paper lies in subtle applications of the Quantitative Sylvester Gallai theorems to prove why projections w.r.t. the \emph{"nice"} subspaces can be ”glued”. We also use Brill's Equations from \cite{GKZ94} 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 \cite{KalTr90}.



ISSN 1433-8092 | Imprint