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 prove super-polynomial lower bounds for low-depth arithmetic circuitsusing the shifted partials measure [Gupta-Kamath-Kayal-Saptharishi, CCC 2013],[Kayal, ECCC 2012] and the affine projections of partials measure[Garg-Kayal-Saha, FOCS 2020], [Kayal-Nair-Saha, STACS 2016]. The recentbreakthrough work of Limaye, Srinivasan and Tavenas [FOCS 2021] proved theselower bounds by proving lower bounds for low-depth set-multilinear circuits. Aninteresting aspect of our proof is that it does not require conversion of acircuit to a set-multilinear circuit, nor does it involve a random restriction.We are able to upper bound the measures for homogeneous formulas directly,without going via set-multilinearity. Our lower bounds hold for the iteratedmatrix multiplication as well as the Nisan-Wigderson design polynomials. Wealso define a subclass of homogeneous formulas which we call unique parse tree(UPT) formulas, and prove superpolynomial lower bounds for these. Thisgeneralizes the superpolynomial lower bounds for regular formulas in[Kayal-Saha-Saptharishi, STOC 2014], [Fournier-Limaye-Malod-Srinivasan, STOC2014].

Low-depth arithmetic circuit lower bounds via shifted partials