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

In their paper on the "chasm at depth four", Agrawal and Vinay have shownthat polynomials in m variables of degree O(m) which admit arithmetic circuitsof size 2^o(m) also admit arithmetic circuits of depth four and size 2^o(m).This theorem shows that for problems such as arithmetic circuit lower bounds orblack-box derandomization of identity testing, the case of depth four circuitsis in a certain sense the general case. In this paper we show that smallerdepth four circuits can be obtained if we start from polynomial size arithmeticcircuits. For instance, we show that if the permanent of n*n matrices hascircuits of size polynomial in n, then it also has depth 4 circuits of sizen^O(sqrt(n)*log(n)). Our depth four circuits use integer constants ofpolynomial size. These results have potential applications to lower bounds anddeterministic identity testing, in particular for sums of products of sparseunivariate polynomials. We also give an application to boolean circuitcomplexity, and a simple (but suboptimal) reduction to polylogarithmic depthfor arithmetic circuits of polynomial size and polynomially bounded degree.

Arithmetic circuits: the chasm at depth four gets wider