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

- 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]

2.
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]

3.
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]

- 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,*Journal of Computer and Systems Sciences*, - 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]

6.
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]

7.
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]

8.
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]

- 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] - T. Opsahl and John H.
Reif, Solving Very Large, Sparse Linear Systems on Mesh-Connected Parallel
Computers.
*First Symposium on Frontiers of Scientific Computing*,

11.
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]

12.
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]

13.
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]

- M. Karr, S. Krishnan,
John H. Reif, Derivation of the Ellipsoid Algorithm, Duke University
Technical Report CS-1991-17, (1990).
[PDF]
- 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]. - S. Krishnan and John H.
Reif, Towards Randomized Streaming, Duke University Technical Report
CS-1991-18. [PDF]
- 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*,*SIAM Journal of Scientific and Statistical Computing*, Vol. 13, No. 1, pp. 119-127, (1992). [PDF]

18.
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]

19.
John H. Reif,
O(log^{2} 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]

20.
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]

- 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. Submitted for journal publication as Space and Time Efficient Implementations of a Parallel Direct Solver using Nested Dissection. [__PDF__]

22.
Victor Y. Pan
and John H. Reif, Generalized Compact Multi-grid, *Computers Math Applications, Volume *25, Number 9, p.3-5, May 1993.
[PDF]

23.
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]

24.
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]

25.
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]

26.
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])

27.
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]

28.
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} 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. Improved Paper
Published as An Efficient Algorithm for the Complex Roots Problem, Journal of
Complexity, 12(2) pp. 81-115, (June 1996). [PostScript] [PDF]