Combinatorial hardness proofs for polynomial evaluation
We exhibit a new method for showing lower bounds for the time complexity of polynomial evaluation procedures. Time, denoted by L, is measured in terms of nonscalar arithmetic operations. The time complexity function considered in this paper is L2. In contrast with known methods for proving lower com...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | , , , |
| Formato: | Acta de conferencia Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
1998
|
| Materias: | |
| Acceso en línea: | Registro en Scopus Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 08227caa a22009497a 4500 | ||
|---|---|---|---|
| 001 | PAPER-12414 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518204237.0 | ||
| 008 | 190411s1998 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-84896693492 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 100 | 1 | |a Aldaz, M. | |
| 245 | 1 | 0 | |a Combinatorial hardness proofs for polynomial evaluation |
| 260 | |c 1998 | ||
| 270 | 1 | 0 | |m Universidad Publica de Navarra, Departamento de Matemática e Informática, 31006 Pamplona, Spain |
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a Aldaz, M., Heintz, J., Matera, G., Montana, J.L., Pardo, L.M., Time-space tradeoffs in algebraic complexity theory (1996) J. of Complexity, , (submitted to) | ||
| 504 | |a Baur, W., Simplified lower bounds for polynomials with algebraic coefficients (1997) J. of Complexity, 13 (1), pp. 38-41 | ||
| 504 | |a Belaga, E.G., Some problems involved in the computations of polynomials (1958) Dokl. Akad. Nauk. SSSR, 123, pp. 775-777 | ||
| 504 | |a Bochnak, J., Coste, M., Roy, M.-F., Géométrie Algébrique Réelle (1987) Ergebnisse der Mathematik und Ihrer Grenzgebiete, 12. , 3. Folge Springer | ||
| 504 | |a Borodin, A., Munro, I., (1975) The Computational Complexity of Algebraic and Numeric Problems, , American Elsevier | ||
| 504 | |a Bürgisser, P., Clausen, M., Shokrollahi, A., Algebraic complexity theory (1997) A Series of Comprehensive Studies in Mathematics, 315. , Springer | ||
| 504 | |a Fitchas, N., Galligo, A., Morgenstern, J., Precise sequential and parallel complexity bounds for the quantifier elimination over algebraically closed fields (1990) J. Pure Appl. Algebra, 67, pp. 1-14 | ||
| 504 | |a Von Zur Gathen, J., Algebraic complexity theory (1988) Ann. Review of Comp. Sci., 3, pp. 317-347 | ||
| 504 | |a Von Zur Gathen, J., Strassen, V., Some polynomials that are hard to compute (1980) Theoret. Comp. Sc., 11 (3), pp. 331-335 | ||
| 504 | |a Heintz, J., On the computational complexity of polynomials and bilinear mappings (1989) Applied Algebra, Algebraic Algorithms and Error-Correcting Codes. Lectures Notes in Computer Science, 356, pp. 269-300. , A survey. L. Huget and A. Poli, editors Springer | ||
| 504 | |a Heintz, J., Morgenstern, J., On the intrinsic complexity of elimination theory (1993) J. of Complexity, 9 (4), pp. 471-498 | ||
| 504 | |a Heintz, J., Schnorr, C.P., Testing polynomials which are easy to compute. Logic and algorithmic: An international symposium held in honor of ernst specker (1982) L'Enseignement de Mathématiques, 30, pp. 237-254. , Genève | ||
| 504 | |a Heintz, J., Sieveking, M., Lower bounds for polynomials with algebraic coefficients (1980) Theoret. Comp. Sc., 11 (3), pp. 321-330 | ||
| 504 | |a Krick, T., Pardo, L.M., A computational method for diophantine approximation (1996) Algorithms in Algebraic Geometry and Applications. Proceedings of MEGA'94, Progress in Mathematics, 143, pp. 193-254. , L. González-Vega and T. Recio, editors Birkhäuser | ||
| 504 | |a Kung, H.T., Traub, J.F., All algebraic functions can be computed fast (1978) J. of the ACM, 25 (2), pp. 245-260 | ||
| 504 | |a Motzkin, T.S., Evaluation of polynomials and evaluation of rational functions (1955) Bull. Amer. Math. Soc., 61, p. 163 | ||
| 504 | |a Pardo, L.M., How lower and upper complexity bounds meet in elimination theory (1995) Applied Algebra, Algebraic Algorithms and Error-Correcting Codes. Proceedings AAECC-11, Lecture Notes in Computer Science, 948, pp. 33-69. , G. Cohen, M. Giusti and T. Mora, editors Springer | ||
| 504 | |a Paterson, M.S., Stockmeyer, L.J., On the number of nonscalar multiplications necessary to evaluate polynomials (1973) SIAM J. of Computing, 2 (1), pp. 60-66 | ||
| 504 | |a Puddu, S., Sabia, J., An effective algorithm for quantifier elimination over algebraically closed fields using straight-line programs J. of Pure Appl. Algebra, , (to appear) | ||
| 504 | |a Schnorr, C.P., Improved lower bounds on the number of multiplications/divisions which are necessary to evaluate polynomials (1978) Theoret. Comp. Sc., 7 (3), pp. 251-261 | ||
| 504 | |a Shoup, V., Smolensky, R., Lower bounds for polynomial evaluation and interpolation problems (1991) Proceedings of the 32nd Annual Symposium FOCS, pp. 378-383. , IEEE Computer Society Press | ||
| 504 | |a Stoss, H.J., On the representation of rational functions of bounded complexity (1989) Theoret. Comp. Sc., 64 (1), pp. 1-13 | ||
| 504 | |a Strassen, V., Polynomials with rational coefficients which are hard to compute (1974) SIAM J. of Computing, 3, pp. 128-149 | ||
| 504 | |a Strassen, V., Algebraic complexity theory (1990) Handbook of Theoretical Computer Science, A, pp. 635-672. , Chap. 11 Elsevier Science Publishers | ||
| 520 | 3 | |a We exhibit a new method for showing lower bounds for the time complexity of polynomial evaluation procedures. Time, denoted by L, is measured in terms of nonscalar arithmetic operations. The time complexity function considered in this paper is L2. In contrast with known methods for proving lower complexity bounds, our method is purely combinatorial and does not require powerful tools from algebraic or diophantine geometry. By means of our method we are able to verify the computational hardness of new natural families of univariate polynomials for which this was impossible up to now. By computational hardness we mean that the complexity function L2 grows linearly in the degree of the polynomials of the family we are considering. Our method can also be applied to classical questions of transcendence proofs in number theory and geometry. A list of (old and new) formal power series is given whose transcendency can be shown easily by our method. © Springer-Verlag Berlin Heidelberg 1998. |l eng | |
| 593 | |a Universidad Publica de Navarra, Departamento de Matemática e Informática, 31006 Pamplona, Spain | ||
| 593 | |a Universidad de Cantabria, Fac. de Ciencias, Depto. de Matemáticas, Est. y Comp., 39071 Santander, Spain | ||
| 593 | |a Universidad de Buenos Aires, FCEyN, Departamento de Matemáticas, (1428) Buenos Aires, Argentina | ||
| 593 | |a Universidad Nacional de Gral. Sarmiento, Instituto de Desarrollo Humano, (1663) San-Miguel, Argentina | ||
| 690 | 1 | 0 | |a ARITHMETIC OPERATIONS |
| 690 | 1 | 0 | |a COMPLEXITY FUNCTIONS |
| 690 | 1 | 0 | |a COMPUTATIONAL HARDNESS |
| 690 | 1 | 0 | |a FORMAL POWER SERIES |
| 690 | 1 | 0 | |a LOWER BOUNDS |
| 690 | 1 | 0 | |a LOWER COMPLEXITY |
| 690 | 1 | 0 | |a POLYNOMIAL EVALUATION |
| 690 | 1 | 0 | |a TIME COMPLEXITY |
| 690 | 1 | 0 | |a ARITHMETIC OPERATIONS |
| 690 | 1 | 0 | |a COMPLEXITY FUNCTIONS |
| 690 | 1 | 0 | |a COMPUTATIONAL HARDNESS |
| 690 | 1 | 0 | |a EXTENDED ABSTRACTS |
| 690 | 1 | 0 | |a FORMAL POWER SERIES |
| 690 | 1 | 0 | |a LOWER COMPLEXITY |
| 690 | 1 | 0 | |a POLYNOMIAL EVALUATION |
| 690 | 1 | 0 | |a TIME COMPLEXITY |
| 690 | 1 | 0 | |a COMPUTER SCIENCE |
| 690 | 1 | 0 | |a FUNCTION EVALUATION |
| 690 | 1 | 0 | |a NUMBER THEORY |
| 690 | 1 | 0 | |a FUNCTION EVALUATION |
| 690 | 1 | 0 | |a NUMBER THEORY |
| 690 | 1 | 0 | |a POLYNOMIALS |
| 690 | 1 | 0 | |a POLYNOMIALS |
| 650 | 1 | 7 | |2 spines |a ALGEBRA |
| 700 | 1 | |a Heintz, J. | |
| 700 | 1 | |a Matera, G. | |
| 700 | 1 | |a Montaña, J.L. | |
| 700 | 1 | |a Pardo, L.M. | |
| 711 | 2 | |c Brno |d 24 August 1998 through 28 August 1998 |g Código de la conferencia: 103183 | |
| 773 | 0 | |d 1998 |g v. 1450 LNCS |h pp. 167-175 |p Lect. Notes Comput. Sci. |n Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |x 03029743 |w (AR-BaUEN)CENRE-983 |z 3540648275 |z 9783540648277 |t 23rd International Symposium on the Mathematical Foundations of Computer Science, MFCS 1998 | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-84896693492&partnerID=40&md5=50d6f80bae43ce90fe4125954ef744b6 |y Registro en Scopus |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_03029743_v1450LNCS_n_p167_Aldaz |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v1450LNCS_n_p167_Aldaz |y Registro en la Biblioteca Digital |
| 961 | |a paper_03029743_v1450LNCS_n_p167_Aldaz |b paper |c PE | ||
| 962 | |a info:eu-repo/semantics/article |a info:ar-repo/semantics/artículo |b info:eu-repo/semantics/publishedVersion | ||
| 963 | |a VARI | ||
| 999 | |c 73367 | ||