• DocumentCode
    2892246
  • Title

    Lower bounds for polynomial evaluation and interpolation problems

  • Author

    Shoup, Victor ; Smolensky, Roman

  • Author_Institution
    Dept. of Comput. Sci., Toronto Univ., Ont., Canada
  • fYear
    1991
  • fDate
    1-4 Oct 1991
  • Firstpage
    378
  • Lastpage
    383
  • Abstract
    It is shown that there is a set of points p1, p2,. . .,pn such that any algebraic program of depth d for polynomial evaluation (or interpolation) at these points has size Ω(n log n/log d). Moreover, if d is a constant, then a lower bound of Ω(n1+1/d) is obtained
  • Keywords
    interpolation; polynomials; symbol manipulation; algebraic program; interpolation problems; lower bound; polynomial evaluation; Arithmetic; Computer science; Costs; Discrete Fourier transforms; Ear; Interpolation; Polynomials;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on
  • Conference_Location
    San Juan
  • Print_ISBN
    0-8186-2445-0
  • Type

    conf

  • DOI
    10.1109/SFCS.1991.185394
  • Filename
    185394
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2892246