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/

Zendy Plus

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

Zendy Tools

Zendy Open

In recent years, a very exciting and promising method for proving lowerbounds for arithmetic circuits has been proposed. This method combines themethod of {\it depth reduction} developed in the works of Agrawal-Vinay [AV08],Koiran [Koi12] and Tavenas [Tav13], and the use of the shifted partialderivative complexity measure developed in the works of Kayal [Kay12] and Guptaet al [GKKS13a]. These results inspired a flurry of other beautiful results andstrong lower bounds for various classes of arithmetic circuits, in particular arecent work of Kayal et al [KSS13] showing superpolynomial lower bounds for{\it regular} arithmetic formulas via an {\it improved depth reduction} forthese formulas. It was left as an intriguing question if these methods couldprove superpolynomial lower bounds for general (homogeneous) arithmeticformulas, and if so this would indeed be a breakthrough in arithmetic circuitcomplexity.  In this paper we study the power and limitations of depth reduction andshifted partial derivatives for arithmetic formulas. We do it via studying theclass of depth 4 homogeneous arithmetic circuits. We show: (1) the first {\itsuperpolynomial lower bounds} for the class of homogeneous depth 4 circuitswith top fan-in $o(\log n)$. The core of our result is to show {\it improveddepth reduction} for these circuits. (2) We show that improved depth reduction{\it is not possible} when the top fan-in is $\Omega(\log n)$. In particularthis shows that the depth reduction procedure of Koiran and Tavenas [Koi12,Tav13] cannot be improved even for homogeneous formulas, thus strengthening theresults of Fournier et al [FLMS13] who showed that depth reduction is tight forcircuits, and answering some of the main open questions of [KSS13, FLMS13].

The Limits of Depth Reduction for Arithmetic Formulas: It's all about the top fan-in