English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We show that over the field of complex numbers, \emph{every} homogeneouspolynomial 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 quitesurprising since there exist homogeneous polynomials $P$ on $n$ variables ofdegree $2$, such that any depth-$3$ arithmetic circuit computing $P$ must havetop fan-in at least $\Omega(n)$.  As an application, we get a new tradeoff between the top fan-in and formaldegree in an approximate analog of the celebrated depth reduction result ofGupta, Kamath, Kayal and Saptharishi [GKKS13]. Formally, we show that if adegree $d$ homogeneous polynomial $P$ can be computed by an arithmetic circuitof 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 ofour 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.

On top fan-in vs formal degree for depth-$3$ arithmetic circuits