Krick, Teresa Straight-line programs in polynomial equation solving. (English) Zbl 1097.65063 Cucker, Felipe (ed.) et al., Foundations of computational mathematics: Minneapolis 2002 (FoCM 2002). Selected papers based on the plenary talks presented at FoCM 2002, Minneapolis, MN, USA, August 5–14, 2002. Cambridge: Cambridge University Press (ISBN 0-521-54253-7/pbk). London Mathematical Society Lecture Note Series 312, 96-136 (2004). Summary: Solving symbolically polynomial equation systems when intermediate and final polynomials are represented in the usual dense encoding turns out to be very inefficient: the sizes of the systems one can deal with do not respond to realistic needs. Evaluation representations appeared in this frame a decade ago as a decade ago as a new possibility to treat new families of problems. We present a survey of the most recent complexity results for different polynomial problems when polynomials are encoded by evaluation (straight-line) programs. We also show surprising mathematical by-products, such as new mathematical invariants and results, that appeared as a consequence of the search of good algorithms.For the entire collection see [Zbl 1084.65004]. Cited in 4 Documents MSC: 65H05 Numerical computation of solutions to single equations 12Y05 Computational aspects of field theory and polynomials (MSC2010) 26C10 Real polynomials: location of zeros 65Y20 Complexity and performance of numerical algorithms 30C15 Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) Keywords:polynomial equation systems; complexity; algorithms Software:Kronecker PDFBibTeX XMLCite \textit{T. Krick}, Lond. Math. Soc. Lect. Note Ser. 312, 96--136 (2004; Zbl 1097.65063)