zbMATH — the first resource for mathematics

Lower bounds for polynomials with algebraic coefficients. (English) Zbl 0452.68051

68Q25 Analysis of algorithms and problem complexity
12D10 Polynomials in real and complex fields: location of zeros (algebraic theorems)
30C15 Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral)
15A06 Linear equations (linear algebraic aspects)
Full Text: DOI
[1] Belaga, E.G., Some problems involved in the computation of polynomials, Dokl. akad. nauk. SSSR, 123, 775-777, (1958) · Zbl 0099.33001
[2] Borodin, A.; Cook, S., On the number of additions to compute specific polynomials, SIAM J. comput., 5, 146-157, (1976) · Zbl 0341.65034
[3] Chandrasekharan, K., Introduction to analytic number theory, () · Zbl 0169.37502
[4] von zur Gathen, J., Personal communication, (1978)
[5] Heintz, J., Definability bounds in algebraically closed fields and a note on degree in affine algebraic geometry, (1977), Preprint
[6] Lang, S., Introduction to algebraic geometry, () · Zbl 0095.15301
[7] Motzkin, T.S., Evaluation of polynomials and evaluation of rational functions, Bull. amer. math. soc., 61, 163, (1955)
[8] Paterson, M.S.; Stockmeyer, L.J., On the number of nonscalar multiplications necessary to evaluate polynomials, SIAM J. comput., 2, 60-66, (1973) · Zbl 0262.65033
[9] Schnorr, C.P., Improved lower bounds on the number of multiplications/divisions which are necessary to evaluate polynomials, Theoret. comput. sci., 7, 251-261, (1978) · Zbl 0387.68034
[10] Schnorr, C.P.; van der Wiele, J.P., On the additive complexity of polynomials, Theoret. comput. sci., 10, 1-18, (1980) · Zbl 0469.68044
[11] Shafarevich, L.R., Basic algebraic geometry, (1972), Nauka Moscow, in English: (Springer, Berlin,1974)
[12] Strassen, V., Polynomials with rational coefficients which are hard to compute, SIAM J. comput., 3, 128-149, (1974) · Zbl 0289.68018
[13] Crelle J. für die reine und angew. Mathematik, 264, 184-202, (1973)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.