|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'506'133
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Reconstruction of Real depth-3 Circuits with top fan-in 2 | | Gaurav Sinha
; | | Date: |
3 Dec 2015 | | Abstract: | We present a polynomial time randomized algorithm for reconstructing
$SigmaPiSigma(2)$ circuits over $mathbb{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 $fin
mathbb{R}[x_1,ldots,x_n]$ of degree d in n variables, 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). Our main techniques are based on the use of Quantitative
Syslvester 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 Brills
Equations([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]. | | Source: | arXiv, 1512.1256 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER