Name
Abstract | ||
|---|---|---|
We show that over the field of complex numbers, emph{every} homogeneous polynomial of degree $d$ can be approximated (in the border complexity sense) by a depth-$3$ arithmetic circuit of top fan-in at most $d+1$. This is quite surprising since there exist homogeneous polynomials $P$ on $n$ variables of degree $2$, such that any depth-$3$ arithmetic circuit computing $P$ must have top fan-in at least $Omega(n)$. As an application, we get a new tradeoff between the top fan-in and formal degree in an approximate analog of the celebrated depth reduction result of Gupta, Kamath, Kayal and Saptharishi [GKKS13]. Formally, we show that if a degree $d$ homogeneous polynomial $P$ can be computed by an arithmetic circuit of size $s$, then for every $t leq d$, $P$ is in the border of a depth-$3$ circuit of top fan-in $s^{O(t)}$ and formal degree $s^{O(d/t)}$. To the best of our knowledge, the upper bound on the top fan-in in the original proof of [GKKS13] is always at least $s^{O(sqrt{d})}$, regardless of the formal degree. |
Year | Venue | DocType |
|---|---|---|
2018 | Electronic Colloquium on Computational Complexity (ECCC) | Journal |
Volume | Citations | PageRank |
25 | 0 | 0.34 |
References | Authors | |
0 | 1 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mrinal Kumar 0001 | 1 | 64 | 9.94 |