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 any Algebraic Branching Program (ABP) computing the polynomial$\sum_{i = 1}^n x_i^n$ has at least $\Omega(n^2)$ vertices. This improves uponthe lower bound of $\Omega(n\log n)$, which follows from the classical resultof Baur and Strassen [Str73, BS83], and extends the results in [K19], whichshowed a quadratic lower bound for \emph{homogeneous} ABPs computing the samepolynomial.  Our proof relies on a notion of depth reduction which is reminiscent ofsimilar statements in the context of matrix rigidity, and shows that any smallenough ABP computing the polynomial $\sum_{i=1}^n x_i^n$ can be depth reducedto essentially a homogeneous ABP of the same size which computes the polynomial$\sum_{i = 1}^n x_i^n + \epsilon(x_1, \ldots, x_n)$, for a structured "errorpolynomial" $\epsilon(x_1, \ldots, x_n)$. To complete the proof, we thenobserve that the lower bound in [K19] is robust enough and continues to holdfor all polynomials $\sum_{i = 1}^n x_i^n + \epsilon(x_1, \ldots, x_n)$, where$\epsilon(x_1, \ldots, x_n)$ has the appropriate structure.  We also use our ideas to show an $\Omega(n^2)$ lower bound of the size ofalgebraic formulas computing the elementary symmetric polynomial of degree$0.1n$ on $n$ variables. This is a slight improvement upon the prior best knownformula lower bound (proved for a different polynomial) of $\Omega(n^2/\log n)$[Nec66, K85, SY10]. Interestingly, this lower bound is asymptotically betterthan $n^2/\log n$, the strongest lower bound that can be proved using previousmethods. This lower bound also matches the upper bound, due to Ben-Or, whoshowed that elementary symmetric polynomials can be computed by algebraicformula (in fact depth-$3$ formula) of size $O(n^2)$. Prior to this work,Ben-Or's construction was known to be optimal only for algebraic formulas ofdepth-$3$ [SW01].

A Quadratic Lower Bound for Algebraic Branching Programs and Formulas