Publications [#332745] of John H. Reif

Conference articles PUBLISHED

1. Reif, J; Tyagi, A, Efficient parallel algorithms for optical computing with the DFT primitive, Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics, vol. 472 LNCS (January, 1990), pp. 149-160, Springer Berlin Heidelberg, ISBN 9783540534877 [doi]
   (last updated on 2026/01/15)

   Abstract:
   The optical computing technology offers new challenges to the algorithm designers since it can perform an n-point DFT computation in only unit time. Note that DFT is a non-trivial computation in the PRAM model. We develop two new models, DFT-VLSIO and DFT-Circuit, to capture this characteristic of optical computing. We also provide two paradigms for developing parallel algorithms in these models. Efficient parallel algorithms for many problems including polynomial and matrix computations, sorting and string matching are presented. The sorting and string matching algorithms are particularly noteworthy. Almost all of these algorithms are within a polylog factor of the optical computing (VLSIO) lower bounds derived in [BR87] and [TR90].