Geodesic
Reducing by 1 the degree of a polynomial with fixed sign function can increase exponentially its weight and length
Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 64 (2009) no. 5, pp. 950-951 
V. V. Podolskii; A. A. Sherstov. Reducing by 1 the degree of a polynomial with fixed sign function can increase exponentially its weight and length. Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 64 (2009) no. 5, pp. 950-951. http://geodesic.mathdoc.fr/item/RM_2009_64_5_a5/
@article{RM_2009_64_5_a5,
     author = {V. V. Podolskii and A. A. Sherstov},
     title = {Reducing by 1 the degree of a polynomial with fixed sign function can increase exponentially its weight and length},
     journal = {Trudy Matematicheskogo Instituta imeni V.A. Steklova},
     pages = {950--951},
     year = {2009},
     volume = {64},
     number = {5},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/RM_2009_64_5_a5/}
}
TY  - JOUR
AU  - V. V. Podolskii
AU  - A. A. Sherstov
TI  - Reducing by 1 the degree of a polynomial with fixed sign function can increase exponentially its weight and length
JO  - Trudy Matematicheskogo Instituta imeni V.A. Steklova
PY  - 2009
SP  - 950
EP  - 951
VL  - 64
IS  - 5
UR  - http://geodesic.mathdoc.fr/item/RM_2009_64_5_a5/
LA  - en
ID  - RM_2009_64_5_a5
ER  - 
%0 Journal Article
%A V. V. Podolskii
%A A. A. Sherstov
%T Reducing by 1 the degree of a polynomial with fixed sign function can increase exponentially its weight and length
%J Trudy Matematicheskogo Instituta imeni V.A. Steklova
%D 2009
%P 950-951
%V 64
%N 5
%U http://geodesic.mathdoc.fr/item/RM_2009_64_5_a5/
%G en
%F RM_2009_64_5_a5

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

[1] M. Goldmann, J. Håstad, A. A. Razborov, Comput. Complexity, 2:4 (1992), 277–300 | DOI | MR | Zbl

[2] R. Beigel, Comput. Complexity, 4:4 (1994), 339–349 | DOI | MR | Zbl

[3] V. V. Podolskii, Computer science – theory and applications, Lecture Notes in Comput. Sci., 5010, Springer, Berlin, 2008, 261–272 | DOI | MR | Zbl