Geodesic
A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials
Sbornik. Mathematics, Tome 203 (2012) no. 10, pp. 1411-1447

Voir la notice de l'article provenant de la source Math-Net.Ru

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. Bibliography: 72 titles.
Keywords: lower bounds for complexity, arithmetic circuits, thin sets, monotone complexity
Mots-clés : permanent. 
@article{SM_2012_203_10_a1,
     author = {S. B. Gashkov and I. S. Sergeev},
     title = {A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials},
     journal = {Sbornik. Mathematics},
     pages = {1411--1447},
     publisher = {mathdoc},
     volume = {203},
     number = {10},
     year = {2012},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2012_203_10_a1/}
}
TY  - JOUR
AU  - S. B. Gashkov
AU  - I. S. Sergeev
TI  - A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials
JO  - Sbornik. Mathematics
PY  - 2012
SP  - 1411
EP  - 1447
VL  - 203
IS  - 10
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SM_2012_203_10_a1/
LA  - en
ID  - SM_2012_203_10_a1
ER  - 
%0 Journal Article
%A S. B. Gashkov
%A I. S. Sergeev
%T A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials
%J Sbornik. Mathematics
%D 2012
%P 1411-1447
%V 203
%N 10
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SM_2012_203_10_a1/
%G en
%F SM_2012_203_10_a1
S. B. Gashkov; I. S. Sergeev. A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials. Sbornik. Mathematics, Tome 203 (2012) no. 10, pp. 1411-1447. http://geodesic.mathdoc.fr/item/SM_2012_203_10_a1/