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 Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Polynomial identity testing and arithmetic circuit lower bounds are twocentral questions in algebraic complexity theory. It is an intriguing fact thatthese questions are actually related. One of the authors of the present paperhas recently proposed a "real {\tau}-conjecture" which is inspired by thisconnection. The real {\tau}-conjecture states that the number of real roots ofa sum of products of sparse univariate polynomials should be polynomiallybounded. It implies a superpolynomial lower bound on the size of arithmeticcircuits computing the permanent polynomial. In this paper we show that thereal {\tau}-conjecture holds true for a restricted class of sums of products ofsparse polynomials. This result yields lower bounds for a restricted class ofdepth-4 circuits: we show that polynomial size circuits from this class cannotcompute the permanent, and we also give a deterministic polynomial identitytesting algorithm for the same class of circuits.

The Limited Power of Powering: Polynomial Identity Testing and a Depth-four Lower Bound for the Permanent