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
Cet article a éte moissonné depuis la source Math-Net.Ru
@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
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/
[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