Papers by Reif on Sequential and Parallel Algebraic and Numerical Algorithms (28 papers)

1.  Richard Barakat and John H. Reif, Numerical Solution of the Fokker-Plank Equation via Chebyschev Approximations with Reference to First Passage Time Probability Functions. Journal of Computational Physics, Vol. 23, No. 4, April 1977, pp. 425-445. [PDF]

  1. John H. Reif, Logarithmic Depth Circuits for Algebraic Functions. 24th Annual IEEE Symposium on Foundations of Computer Science, Tucson, AZ, November 1983, pp. 138-145. Published in SIAM Journal on Computing, Vol. 15, No. 1, February 1986, pp. 231-242. [PDF]
  2. John H. Reif, Probabilistic Parallel Prefix Computation, 13th Annual International Conference on Parallel Processing, Michigan, 1984. Published in Computers and Mathematics with Applications, Vol. 26, Number 1, July 1993, pp. 101-110. [PDF]

4.  Micheal Ben-Or, Dextor Kozen, and John H. Reif, The Complexity of Elementary Algebra and Geometry. 16th Annual Symposium on Theory of Computing, Washington, DC, April-May 1984, pp. 457-464. [PDF] Published in Journal of Computer and Systems Sciences, Vol. 32, No. 2, April 1986, pp. 251-264. [PDF]

5.  John H. Reif and J.D. Tygar, Efficient Parallel Pseudo-random Number Generation. CRYPTO-85, Proceedings, Vol. 218, H. Williams and E. Brickell, ed., Springer-Verlag, New York, NY, 1986, pp. 433-446 Presented at the Mathematical Theory of Security, Boston, MA, 1985. Published in SIAM Journal on Computing, Vol. 17, No. 2, April 1988, pp. 404-411. [PDF]

  1. Victor Y. Pan and John H. Reif, Efficient Parallel Solution of Linear Systems. 17th Annual ACM Symposium on Theory of Computing(STOC 85), Providence, RI, May 1985, pp. 143-(ACM Press, New York) 152. Presented at the meeting on Efficient Algorithms, Mathematisches Forschungsinstitut, Oberwolfach, W. Germany, November 1984. Presented at 2nd SIAM Conference on Applied Linear Algebra, Raleigh, NC, April 1985. Published as Fast and Efficient Parallel Solution of Sparse Linear Systems. SIAM Journal on Computing, Vol. 22, No. 6, pp. 1227-1250, December 1993. [PDF] or [PDF]
  2. Victor Y. Pan and John H. Reif, Fast and Efficient Algorithms for Linear Programming and for the Linear Least Squares Problem, 12th International Symposium on Mathematical Programming, MIT, Cambridge, MA, pp. 283-295, August 1985. Abstract published as Efficient Parallel Linear Programming, Operations Research Letters, Vol. 5, No. 3, August 1986, pp. 127-135. [PDF] Also presented as Fast and Efficient Parallel Linear Programming and Least Squares Computations at Aegean Workshop on Computing, Loutraki, Greece, July 1986; Lecture Notes in Computer Science, Springer-Verlag, Vol. 227, 1986, pp. 283-295. Full Paper published as Fast and Efficient Linear Programming and Linear Least-Squares Computations, Computers and Mathematics with Applications, Vol. 12A, No. 12, 1986, pp. 1217-1227. [PDF]
  3. Victor Y. Pan and John H. Reif, Fast and Efficient Parallel Solution of Dense Linear Systems. Computers and Mathematics with Applications, Vol. 17, No. 11, 1989, pp. 1481-1491. [PDF]

9.  Charles E. Leiserson, J.P. Mesirov, L. Nekludova, S.M. Omohundro, John H. Reif, and W. Taylor, Solving Sparse Systems of Linear Equations on the Connection Machine. Annual SIAM Conference, Boston, MA, July 1986. [PDF]

10.                 T. Opsahl and John H. Reif, Solving Very Large, Sparse Linear Systems on Mesh-Connected Parallel Computers. First Symposium on Frontiers of Scientific Computing, NASA, Goddard Space Flight Center, Greenbelt, MD, September 1986, pp. 2241-2248. [PDF]

  1. John H. Reif and Steve R. Tate, On Threshold Circuits and Polynomial Computation. 2nd Structure in Complexity Theory Conference, Ithaca, NY, June 1987. Published in SIAM Journal on Computing, Vol.21, No. 5, October 1992, 896-908. [PDF] or [PostScript] [PDF]
  2. Victor Y. Pan and John H. Reif, Some Polynomial and Toeplitz Matrix Computations. 28th Annual IEEE Symposium on Foundations of Computer Science, Los Angeles, CA, October 1987, (IEEE Computer Society Press) pp. 173-184. [PDF]
  3. John H. Reif and Steve R. Tate, Optimal Size Integer Division Circuits. 21st Annual ACM Symposium on Theory of Computing, Seattle, WA, May 1989, pp. 264-273. Presented at meeting on Efficient Algorithms, Mathematisches Forschungsinstitut, W. Germany, September 1989. Published in SIAM Journal on Computing, Vol. 19, No. 5, October 1990, pp. 912-924. [PDF] or [PostScript] [PDF] or [PostScript]

14.                 M. Karr, S. Krishnan, John H. Reif, Derivation of the Ellipsoid Algorithm, Duke University Technical Report CS-1991-17, (1990).  [PDF]

15.                 Victor Y. Pan and John H. Reif, On the Bit-Complexity of Discrete Approximations to PDEs. International Colloquium on Automata, Languages, and Programming(ICALP 90), Warwich, England, Springer Lecture Notes in Computer Science 443, pp. 612-625, July 1990. [PDF] Published as The Bit-Complexity of Discrete Solutions of Partial Differential Equations: Compact Multigrid, Computers and Mathematics with Applications, Vol. 20, No. 2, 1990, pp. 9-16. [PDF].

16.                 S. Krishnan and John H. Reif, Towards Randomized Streaming, Duke University Technical Report CS-1991-18. [PDF]

17.                 Victor Y. Pan and John H. Reif, Decreasing the Precision of Linear Algebra Computations by Using Compact Multigrid and Backward Interval Analysis. 4th SIAM Conference in Applied Linear Algebra, Minneapolis, MN, September 1991. Published as Compact Multigrid, SIAM Journal of Scientific and Statistical Computing, Vol. 13, No. 1, pp. 119-127, (1992). [PDF]

  1. J. Cheriyan and John H. Reif, Parallel and Output Sensitive Algorithms for Combinatorial and Linear Algebra Problems, 1992. 4th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA'93), Velon, Germany, July 1993, p.50-56. Published as John H. Reif, Parallel Output Sensitive Algorithms for Combinatorial and Linear Algebra Problems, Journal of Computer and System Sciences, Vol. 62, May 2001, pp. 398-412. [PostScript] [PDF]
  2. John H. Reif, O(log2 n) Time Efficient Parallel Factorization of Dense, Sparse Separable, and Banded Matrices. 5th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA'94), Cape May, NJ, June 1994, pp. 114-121. [PostScript] [PDF]
  3. John H. Reif, An O(n log^3 n) Algorithm for the Real Root Problem. 34th Annual IEEE Conference on Foundations of Computer Science (FOCS '93) Proceedings, November 1993, Palo Alto, CA, pp. 626-635. Revised as An Efficient Algorithm for the Real Root and Symmetric Tridiagonal Eigenvalue Problems, 1994. [PostScript] [PDF] and [PostscriptFigures]
  4. Deganit Armon and John H. Reif, Space and time efficient implementations of parallel nested dissection, 1992. 4th Annual ACM Symposium on Parallel Algorithms and Architectures, San Diego, CA, July 1992. [PDF]
  5. Victor Y. Pan and John H. Reif, Generalized Compact Multi-grid, Computers Math Applications, Volume 25, Number 9, p.3-5, May 1993. [PDF]
  6. John H. Reif and Steve R. Tate, Dynamic Algebraic Algorithms, Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'94), TX, Jan. 1994. pp.290-301. Published as On Dynamic Algorithms for Algebraic Problems, Journal of Algorithms, Volume 22, Number 2, pp. 347-371, February 1997. [PostScript] [PDF]
  7. John H. Reif, Efficient Parallel Solution of Sparse Eigenvalue and Eigenvector Problems, Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science (FOCS'95) Milwaukee, WI, October 23-25, 1995, pp. 123-132. Published as Efficient Parallel Computation of the Characteristic Polynomial of a Sparse, Separable Matrix, Algorithmica, 29: pp, 487-510 (2001). [PostScript] [PDF]
  8. John H. Reif, Work Efficient Parallel Solution of Toeplitz Systems and Polynomial GCD. Proc. of the 27th ACM Symposium on Theory of Computing (STOC 95), Las Vegas, NV, May 29-June 1, 1995, pp. 751-761. Revised as Efficient Parallel Factorization and Solution of Structured and Unstructured Linear Systems, Journal of Computer and System Sciences, Vol. 71, Issue 1 (July 2005), pp. 86 - 143. [PDF] [PDF]
  9. John H. Reif, Efficient Approximate Solution of Sparse Linear Systems, Published in Computers and Mathematics with Applications, Vol. 36, No. 9, Nov. 1998, pp. 37-58. [PostScript] [PDF] (Also, see errata, Computers and Mathematics with Applications, Vol. 38, No. 9, 1999, pp. 141-141. [PDF])
  10. John H. Reif, Approximate Complex Polynomial Evaluation in Near Constant Work Per Point. Proc. 29th ACM Symposium on Theory of Computing (STOC97), El Paso, Texas, pp. 30-39 (May 4-6, 1997). Published in SIAM Journal of Computing (SICOMP), Vol. 28. Number 6, pp. 2059-2089, 1999. [PostScript] [PDF]
  11. Andrew Neff and John H. Reif, An O(n^{1+epsilon} log b) Algorithm for the Complex Roots Problem. 35th Annual IEEE Conference on Foundations of Computer Science (FOCS '94) Proceedings, Santa Fe, NM, November 1994. pp. 540-547. Andrew Neff and John H. Reif, An O(n^{1+epsilon} logb) Algorithm for the Complex Roots Problem. 35th Annual IEEE Conference on Foundations of Computer Science (FOCS '94) Proceedings, Santa Fe, NM, November 1994. pp. 540-547. Improved Paper Published as An Efficient Algorithm for the Complex Roots Problem, Journal of Complexity, 12(2) pp. 81-115, (June 1996). [PostScript] [PDF]