Llower bounds for the complexity of monotone arithmetic circuits computing real polynomials

What is it about?

This work suggests a method for deriving lower bounds for the complexity of polynomials with positive real coefficients implemented by circuits of functional elements over the monotone arithmetic basis $ \{x+y, \,x \cdot y\}\cup\{a \cdot x\mid a\in \mathbb R_+\}$. Using this method, several new results are obtained. In particular, we construct examples of polynomials of degree $ m-1$ in each of the $ n$ variables with coefficients 0 and 1 having additive monotone complexity $ m^{(1-o(1))n}$ and multiplicative monotone complexity $ m^{(1/2-o(1))n}$ as $ m^n \to \infty$. In this form, the lower bounds derived here are sharp.

Featured Image