ECCC-Report TR18-068https://eccc.weizmann.ac.il/report/2018/068Comments and Revisions published for TR18-068en-usMon, 09 Apr 2018 17:47:40 +0300
Revision 1
| On top fan-in vs formal degree for depth-3 arithmetic circuits |
Mrinal Kumar
https://eccc.weizmann.ac.il/report/2018/068#revision1We show that over the field of complex numbers, 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.Mon, 09 Apr 2018 17:47:40 +0300https://eccc.weizmann.ac.il/report/2018/068#revision1
Paper TR18-068
| On top fan-in vs formal degree for depth-3 arithmetic circuits |
Mrinal Kumar
https://eccc.weizmann.ac.il/report/2018/068We show that over the field of complex numbers, 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.Mon, 09 Apr 2018 08:10:06 +0300https://eccc.weizmann.ac.il/report/2018/068