Publications [#236965] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Reif, JH; Tate, SR, Dynamic algebraic algorithms, Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms (January, 1994), pp. 290-301 [pdf]
   (last updated on 2026/01/14)

   Abstract:
   The authors examine the problem of incrementally evaluating algebraic functions. The paper presents both lower bounds and algorithm design techniques for algebraic problems. The first presentation deals with the lower bounds for simply stated algebraic problems: multipoint polynomial evaluation, polynomial reciprocal, and extended polynomial GCD. The second deals with two general purpose techniques for designing incremental algorithms. The first method can produce highly efficient incremental algorithms and the second method gives a slightly slower incremental algorithm for these problems but can be applicable to a wider class of problems than the first method.