J. H. Reif and H. R. Lewis, Symbolic Evaluation and the Global Value Graph



Download 157.8 Kb.
Page1/2
Date20.10.2016
Size157.8 Kb.
#6468
  1   2

Books


1. VLSI Algorithms and Architectures, 3rd Aegean Workshop on Computing, AWOC 88, Corfu, Greece, June-July 1988.

2. Synthesis of Parallel Algorithms. 22 chapters, 1011 pages. Published by Morgan Kaufmann, San Mateo, California, 1993.

3. Parallel Algorithm Derivation and Program Transformation, (Edited by R. Paige, J. Reif, and R. Wachter), 228 pages. Published by Kluwer Academic Publishers, 1993.

4. Handbook of Randomized Computing (Edited by S. Rajasekaran, P. M. Pardalos, J.H. Reif and J. Rolim), Kluwer Volume I and II, Academic Press, London, 2001.



5. Junghuei Chen and John Reif, Editors, Ninth International Meeting on DNA Based Computers (DNA9), Madison, Wisconsin, June 2-4, 2003, Lecture Notes in Computer Science Vol. 2943, Springer-Verlag, New York, (2004).

Papers (97 downloadable out of total of 195 papers)

  1. J.H. Reif, Combinatorial Aspects of Symbolic Program Analysis. Ph.D. Thesis, Harvard University, July 1977.

  2. R. Barakat and J.H. Reif, Numerical Solution of the Folker-Plank Equation via Chebyschev Approximations with Reference to First Passage Time Probability Functions. Published in Journal of Computational Physics, Vol. 23, No. 4, April 1977, pp. 425-445.

  3. J.H. Reif and H.R. Lewis, Symbolic Evaluation and the Global Value Graph. 4th ACM Symposium on Principals of Programming Languages, Los Angeles, CA, January 1977, pp. 104-118. [PDF] Published as Efficient Symbolic Analysis of Programs, in Journal of Computer and System Sciences, Vol. 32, No. 3, June 1986, pp. 280-314.

  4. J.H. Reif, Code Motion. Presented at Conference on Theoretical Computer Science, University of Waterloo, Canada, 1977. Published in SIAM Journal on Computing, Vol. 9, No. 2, May 1980, pp. 375-395.

  5. J.H. Reif, Symbolic Program Analysis in Almost Linear Time. 5th Annual ACM Symposium on Principals of Programming Languages, Tucson, AZ, January 1978, pp. 76-83. [PDF] Published as J.H. Reif and R.E. Tarjan, SIAM Journal on Computing, Vol. 11, No. 1, February 1982, pp. 81-93.

  6. J.H. Reif, Data Flow Analysis of Communicating Processes. 6th Annual ACM Symposium on Principals of Programming Languages, San Antonio, TX, January 1979, pp. 257-268. [PDF] Published as J.H. Reif and S. Smolka, International Journal of Parallel Programming, Vol. 19, No. 1, February 1990.

  7. J.H. Reif, The Complexity of Extending a Graph Imbedding. Computer Science Department, University of Rochester, TR-42, October 1978.

  8. G. Miller, I. Filotti, and J.H. Reif, On Determining the Genus of a Graph in 0(v0(g)) Steps, 11th Annual ACM Symposium on Theory of Computing, Atlanta, GA, April 1979, pp. 27-37.

  9. J.H. Reif, Universal Games of Incomplete Information. 11th Annual ACM Symposium on Theory of Computing, Atlanta, GA, April 1979, pp. 288-308. Harvard University TR-35-81. [PDF] Published as The Complexity of Two Player Games of Incomplete Information. Journal of Computer and System Sciences, Vol. 29, No. 2, October 1984, pp. 274-301.

  10. G.L. Peterson and J.H. Reif, Multiple-Person Alternation. 20th Annual IEEE Symposium on Foundations of Computer Science, San Juan, Puerto Rico, October 1979, pp. 348-363. Published as G.L. Peterson, J.H. Reif, and S. Azhar, Lower Bounds for Multiplayer Non-Cooperative Games of Incomplete Information. in Computers and Mathematics with Applications, Volume 41, April 2001, pp 957-992. [PostScript] [PDF]

  11. J.H. Reif, Complexity of the Mover's Problem and Generalizations. 20th Annual IEEE Symposium on Foundations of Computer Science, San Juan, Puerto Rico, October 1979, pp. 421-427. Published as Complexity of the Generalized Mover's Problem, Chapter 11 in Planning, Geometry and Complexity of Robot Motion, Jacob Schwartz, ed., Ablex Pub., Norwood, NJ, 1987, pp. 267-281.

  12. G.L. Peterson and J.H. Reif, A Dynamic Logic of Multiprocessing with Incomplete Information. 7th Annual ACM Symposium on Principals of Programming Languages, Las Vegas, NV, January 1980, pp. 193-202. [PDF]

  13. J.H. Reif, Logics for Probabilistic Programming. 12th Annual ACM Symposium on Theory of Computing, Los Angeles, CA, April 1980, pp. 8-13. [PDF]

  14. J.H. Reif and P. Spirakis, Random Matroids. 12th Annual ACM Symposium on Theory of Computing, Los Angeles, CA, April 1980, pp. 385-397. [PDF] Revised as Harvard University TR-28-81, Probabilistic Analysis of Random Extension-Rotation Algorithms.

  15. J.H. Reif and P. Spirakis, Distributed Algorithms for Synchronizing Interprocess Communication Within Real Time. 13th Annual ACM Symposium on Theory of Computing, Milwaukee, WI, 1981, pp. 133-145. Published as Real-Time Synchronization of Interprocess Communications: ACM Journal of Transactions on Programming Languages and Systems, Vol. 6, No. 2, April 1984, pp. 215-238. [PDF]

  16. J.H. Reif, Minimum s-t Cut of Planar Undirected Network in 0(n log2n) Time, 8th Colloquium on Automata, Languages and Programming, (Shimon Even and Oded Kariv, editors) volume 115 of Lecture Notes in Computer Science, pages 56-67, Acre (Akko), Israel, 13-17 July 1981. Springer-Verlag. Published in SIAM Journal on Computing, Vol. 12, No. 1, February 1983, pp. 71-81.

  17. J.H. Reif, Symmetric Complementation. 14th Annual ACM Symposium on Theory of Computing, San Francisco, CA, May 1982, pp. 201-214. Presented at the NSF/AMS on Probabilistic Computational Complexity, Durham, NH, June 1982. Published in Journal of the ACM(JACM), Vol. 31, No. 2, April 1984, pp. 401-421. [PDF]

  18. J.Y. Halpern and J.H. Reif, The Propositional Dynamic Logic of Deterministic, Well-Structured Programs, 22nd Annual IEEE Symposium on Foundations of Computer Science, Nashville, TN, October 1981, pp. 322-334. Published in Journal of Theoretical Computer Science, Vol. 27, 1983, pp. 127-165. [PDF]

  19. J.H. Reif and P. Spirakis, Unbounded Speed Variability in Distributed Communication Systems. 9th Annual ACM Symposium on Principals of Programming Languages, Albuquerque, NM, January 1982, pp. 46-56. [PDF] Published in SIAM Journal on Computing, Vol. 14, No. 1, February 1985, pp. 75-92.

  20. G.L. Peterson and J.H. Reif, Decision Algorithms for Multiplayer Games of Incomplete Information. Harvard University, TR-34-81. Published as G.L. Peterson, J.H. Reif, and S. Azhar, Decision Algorithms for Multiplayer Non-Cooperative Games of Incomplete Information. Computers and Mathematics with Applications, Vol. 43, Jan. 2002, pp 179-206. [PostScript] [PDF]

  21. J.H. Reif and P. Spirakis, K-connectivity in Random Undirected Graphs, Discrete Mathematics, Vol. 54, No. 2, April 1985, pp. 181-191. [PDF]

  22. J.H. Reif and P. Spirakis, Strong k-connectivity in Digraphs and Random Digraphs, Harvard University TR-25-81.

  23. J.H. Reif, On the Power of Probabilistic Choice in Synchronous Parallel Machines. Harvard University TR-30-81. 9th International Colloquium on Automata, Languages and Programming, Aarhus, Denmark, 1982, pp. 442-450. Published as On Synchronous Parallel Computations with Independent Probabilistic Choice in SIAM Journal on Computing, Vol. 13, No. 1, February 1984, pp. 46-56.

  24. J.H. Reif and P. Spirakis, Real Time Resource Allocation in Distributed Systems, ACM Symposium on Principals of Distributed Computing, Ottawa, Canada, August 1982, pp. 84-94. [PDF]

  25. J.H. Reif, Parallel Time 0(log n) Time Acceptance of Deterministic CFLs. 23rd Annual IEEE Symposium on Foundations of Computer Science, Chicago, IL, November 1982, pp. 290-296. Published as P. Klein and J.H. Reif, Parallel Time 0(log n) Time Acceptance of Deterministic CFLs on an Exclusive-Write P-RAM, SIAM Journal on Computing, Vol. 17, No. 3, June 1988, pp. 463-485.

  26. J.H. Reif and P. Spirakis, Expected Parallel Time and Sequential Space Complexity of Graph and Digraph Problems, Published in Algorithmica, Special Issue on Graph Algorithms, Vol. 7, Numbers 5 & 7, pp. 597-630, 1992.

  27. L.G. Valiant and J.H. Reif, A Logarithmic Time Sort for Linear Size Networks. 15th Annual ACM Symposium on Theory of Computing, Boston, MA, April 1983, pp. 10-16. [PDF] Published in Journal of the ACM(JACM), Vol. 34, No. 1, January 1987, pp. 60-76. [PDF]

  28. J.H. Reif and W.L. Scherlis, Deriving Efficient Graph Algorithms. Logics of Programs Workshop, Carnegie-Mellon University, Pittsburgh, PA, June 1983, Lecture Notes in Computer Science, Vol. 164, 1984, pp. 421-441. Published in: Verification: Theory and Practice: Essays Dedicated to Zohar Manna on the Occasion of His 64th Birthday (edited by Nachum Dershowitz), LNCS series Vol. 2772, pp 645-681, 2004. [PDF] or [PDF]

  29. J.H. Reif and A.P. Sistla, A Multiprocess Network Logic with Temporal and Spatial Modalities, 10th International Colloquium on Automata, Languages and Programming, Barcelona, Spain, July 1983; Lecture Notes in Computer Science, Vol. 154, 1983, pp. 629-639. Published in Journal of Computer and System Sciences, Vol. 30, No. 1, February 1985, pp. 41-53.

  30. J.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.

  31. J.H. Reif, An n1+epsilon Processor, 0(logn) Time Probabilistic Sorting Algorithm Abstract. SIAM 2nd Conference on the Applications of Discrete Mathematics, Cambridge, MA, June 1983, p. 27-29.

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

  33. J.H. Reif and P. Spirakis, Probabilistic Bidding Gives Optimal Distributed Resource Allocation. 11th International Colloquium on Automata, Languages and Programming, Antwerp, Belgium, July 1984. Published in Lecture Notes in Computer Science, Vol. 172, pp. 391-402.

  34. J.H. Reif, Depth-First Search is Inherently Sequential. Information Processing Letters, Vol. 20, No. 5, June 12, 1985, pp. 229-234. [PDF]

  35. J.H. Reif, A Topological Approach to Dynamic Graph Connectivity. Information Processing Letters, Vol. 25, No. 1, April 20, 1987, pp. 65-70. [PDF]

  36. G. Kar, C.N. Nikolaou, and J.H. Reif, Assigning Processes to Processors: A Fault-Tolerant Approach, 14th International Conference on Fault-Tolerant Computing, Kissimmee, FL, June 1984.

  37. M. Ben-Or, D. Kozen, and J.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.

  38. R. Nair, A. Bruss, and J.H. Reif, Linear Time Algorithms for Optimal CMOS Layout, International Workshop on Parallel Computing and VLSI, Amalfi, Italy, May 1984; VLSI: Algorithms and Architectures, North-Holland pub., pp. 327-338.

  39. J.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.

  40. P. Gacs and J.H. Reif, A Simple Three-dimensional Real-time Reliable Cellular Array. 17th Annual ACM Symposium on Theory of Computing, Providence, RI, May 1985, pp. 388-395. [PDF] Published in Journal of Computer and System Sciences, Vol. 36, No. 2, April 1990, pp. 125-147.

  41. V. Pan and J.H. Reif, Efficient Parallel Solution of Linear Systems. 17th Annual ACM Symposium on Theory of Computing(STOC85), Providence, RI, (ACM Press, New York) May 1985, pp. 143-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. [PostScript] [PDF]

  42. G. Miller and J.H. Reif, Parallel Tree Contraction and its Application. Harvard University TR-18-85. 26th Annual IEEE Symposium on Foundations of Computer Science, Portland, OR, October 1985, pp. 478-489.

42a Portions Published as Parallel Tree Contraction Part I: Fundamentals, Advances in Computing Research, Vol. 5., pp. 47-72, 1989. [PDF]

42b Portions Published as Parallel Tree Contraction Part II: Further Applications, SIAM Journal on Computing, Vol. 20, No. 6, pp. 1128-1147, December 1991. [PDF]



  1. S. Rajasekaran and J.H. Reif, An Optimal Parallel Algorithm for Integer Sorting. 26th Annual IEEE Symposium on Foundations of Computer Science, Portland, OR, October 1985, pp. 496-503. Published as Optimal and Sublogarithmic Time Randomized Parallel Sorting Algorithms, SIAM Journal on Computing, Vol. 18, No. 3, June 1989, pp. 594-607. [PostScript] [PDF]

  2. J.H. Reif and M. Sharir, Motion Planning in the Presence of Moving Obstacles, 26th Annual IEEE Symposium on Foundations of Computer Science, Portland, OR, October 1985, pp. 144-154. Published in Journal of the ACM (JACM), 41:4, July 1994, pp. 764-790. [PDF] or [PostScript] [PDF]

  3. J.H. Reif, Probabilistic Algorithms in Group Theory. Foundations of Computation Theory (FCT85), Cottbus, Democratic Republic of Germany, September 1985; appeared in Lecture Notes in Computer Science, Vol. 199, 1985, pp. 341-350. Also TR85-01, Dept. of Computer Science, Harvard University, (1985). Published as S. Azhar and J.H. Reif, Efficient Algorithmic Learning of the Structure of Permutation Groups by Examples, Computers & Mathematics with Applications, Volume 37, Issue 10, May 1999, pp 105-132. [PostScript] [PDF]

  4. V. Pan and J.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, August 1985. 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.

46a An abstract of this paper appears as Efficient Parallel Linear Programming, Operations Research Letters, Vol. 5, No. 3, August 1986, pp. 127-135. [PDF]

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



  1. J.H. Reif, The Very Unusual Behavior of Parallel Interpolation Search. 23rd Annual Allerton Conference on Communication, Control and Computing, Monticello, IL, October 1985. Published as D.E. Willard and J.H. Reif, Parallel Processing can be Harmful: the Unusual Behavior of Interpolation Search, Journal of Information and Computation, Vol. 81, No. 3, June 1989, pp. 364-379.

  2. J.H. Reif and S. Smolka, The Complexity of Reachability in Distributed Communicating Processes, Journal of Acta Informatica, Vol. 25(3), April 1988, pp.333-354.

  3. S. Homer and J.H. Reif, Arithmetic Theories for Computational Complexity Problems, Journal of Information and Control, Vol. 69, nos. 1-3, April/May/June 1986, pp. 1-11.

  4. J.A. Storer and J.H. Reif, A Parallel Architecture for High Speed Data Compression, 3rd Symposium on the Frontiers of Massively Parallel Computation, College Park, MD, October 1990, pp. 238-243. Published in Journal of Parallel and Distributed Computation, 13, 1991, pp 222-227. [PDF]

  5. V. Pan and J.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]

  6. J.H. Reif and J.A. Storer, Shortest Paths in Euclidean Space with Polyhedral Obstacles. Symposium on Mathematical Foundations of Computer Science, Czechoslovakia, August 1988. Published as Shortest Paths in the plane with polygonal obstacles, Journal of the ACM(JACM) 41:5, September, 1994, pp. 982-1012. [PDF]

  7. J.H. Reif and J.A. Storer, Minimizing Turns for Discrete Movement in the Interior of a Polygon, IEEE Journal of Robotics and Automation, Vol. 3, No. 3, June 1987, pp. 182-193. [PDF]

  8. J.H. Reif, Efficient VLSI Fault Simulation. Computers and Mathematics with Applications, Vol 25, No. 2, Jan. 1993, pp. 15-32. [PDF]

  9. R.E. Ladner and J.H. Reif, The Logic of Distributed Protocols. Conference on Theoretical Aspects of Reasoning about Knowledge, Los Altos, CA, March 1986, pp. 207-223. [PDF]

  10. V. Pan and J.H. Reif, Extension of the Parallel Nested Dissection Algorithm to Path Algebra Problems. Presented at 6th Conference on Foundation of Software Technology and Theoretical Computer Science, New Delhi, India; Lecture Notes in Computer Science, Springer Verlag, Vol. 241, 1986. An abstract of this paper appears as Parallel Nested Dissection for Path Algebra Computations, Operations Research Letters, Vol. 5, No. 4, October 1986, pp. 177-184. [PDF] Published as Fast and Efficient Solution of Path Algebra Problems, Journal of Computer and Systems Sciences, Vol. 38, No. 3, June 1989, pp. 494-510.

  11. J. Canny and J.H. Reif, New Lower Bound Techniques for Robot Motion Planning Problems. 28th Annual IEEE Symposium on Foundations of Computer Science, Los Angeles, CA, October 1987, pp. 49-60. [PDF]

  12. R. Barakat and J.H. Reif, Lower Bounds on the Computational Efficiency of Optical Computing Systems. Journal of Applied Optics, Vol. 26, No. 6, March 15, 1987, pp. 1015-1018.

  13. R. Barakat and J.H. Reif, Polynomial Convolution Algorithm for Matrix Multiplication with Application for Optical Computing. Published in Journal of Applied Optics, Vol. 26, No. 14, July 15, 1987, pp. 2707-2711.

  14. J.H. Reif, A Survey on Advances in the Theory of Computational Robotics. Appeared in the Proceedings of the Fourth Workshop of Adaptive Systems Control Theory as Adaptive and Learning Systems: Theory and Applications, K.S. Narendra, ed., Plenum Press, New York, NY, 1986.

  15. P. Klein and J.H. Reif, An Efficient Parallel Algorithm for Planarity. 27th Annual IEEE Symposium on Foundations of Computer Science, Toronto, Canada, October 1986, pp. 465-477. Published in Journal of Computer and System Sciences, Vol. 37, No. 2, October 1988, pp. 190-246.

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

  17. T. Opsahl and J.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.

  18. S. Kasif, J.H. Reif and D. Sherlekar, Formula Dissection: A Parallel Algorithm for Constraint Satisfaction. IEEE Workshop on Computer Architecture for Pattern Analysis and Machine Intelligence, Seattle, WA, October 1987, pp. 51-58.

  19. J.H. Reif and S. Sen, Optimal Randomized Parallel Algorithms for Computational Geometry. 16th International Conference on Parallel Processing, St. Charles, IL, August 1987, pp. 270-276. Published in Algorithmica, Vol. 7, No. 1, January 1992, pp. 91-117. [PDF]

  20. J. Canny, B. Donald, J.H. Reif and P. Xavier. On the Complexity of Kinodynamic Planning. 29th Annual IEEE Symposium on Foundations of Computer Science, White Plains, NY, October 1988, pp. 306-316. Published as Kinodynamic Motion Planning, Journal of the ACM, Vol 40(5), November 1993, pp. 1048-1066. [PDF]

  21. S. Rajasekaran and J.H. Reif, Randomized Parallel Computation. Presented at Foundations of Computation Theory Conference, Kasan, USSR, June 1987; Lecture Notes in Computer Science, Vol. 278, 1987, pp. 364-376. Published in Chapter 11 of Concurrent Computations: Algorithms, Architecture and Technology, S.K. Tewksbury, B.W. Dickinson and S.C. Schwartz, ed., 1988, pp. 181-202. [PDF]

  22. J.H. Reif and S. 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. [PostScript] [PDF] or [PostScript]

  23. V. Ramachandran and J.H. Reif, An Optimal Parallel Algorithm for Graph Planarity. 30th Annual IEEE Symposium on Foundations of Computer Science, Research Triangle Park, NC, October 1989, pp. 282-287. Published in Journal of Computer and System Sciences, 49:3, December, 1994, pp. 517-561. [PostScript] [PDF] or [PostScript]

  24. S. Rajasekaran and J.H. Reif, Nested Annealing: A Provable Improvement to Simulated Annealing. Presented at Workshop on Applications of Combinatorics and Graph Theory to Computer Science, Institute for Mathematics and its Applications, University of Minnesota, December 1987. Presented at the 15th International Colloquium on Automata, Languages and Programming, Tampere, Finland, July 1988; Lecture Notes in Computer Science, Vol. 317, 1988, pp. 455-472. Published in Journal of Theoretical Computer Science, 99(1):157-176, 1 June 1992. [PDF]

  25. V. Pan and J.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.

  26. J.A. Storer and J.H. Reif, Real-time Compression of Video on a Grid-connected Parallel Computer. 3rd International Conference on Supercomputing, Boston, MA, May 1988. [PDF]

  27. E.W. Davis and J.H. Reif, Architecture and Operation of the BLITZEN Processing Element. 3rd International Conference on Computing on Supercomputing, Boston, MA, May 1988. Also as D.W. Blevin, E.W. Davis and J.H. Reif, Processing Element and Custom Chip Architecture for the BLITZEN Massively Parallel Processor, MCNC Technical Report TR87-22, October 1987, revised June 1988.

  28. J.H. Reif and S. Sen, An Efficient Output-Sensitive Hidden-Surface Removal Algorithm and its Parallelization. 4th Annual ACM Symposium on Computational Geometry, Urbana, IL, June 1988, pp. 193-200. Published as An Efficient Output-Sensitive Hidden-Surface Removal Algorithm for Polyhedral Terrains, Journal of Mathematical and Computer Modeling, Vol. 21, No. 5, pp. 89-104, 1995. [PDF] or [PDF]

  29. L.S. Nyland and J.H. Reif, An Algebraic Technique for Generating Optimal CMOS Circuitry in Linear Time, Computers and Mathematics with Applications Vol 31, No. 1, Jan. 1996, pp.85-108. [PDF]

  30. D.W. Blevins, E.W. Davis, R.A. Heaton and J.H. Reif, BLITZEN: A Highly Integrated Massively Parallel Machine. 2nd Symposium on Frontiers of Massively Parallel Computation, Fairfax, VA, October 1988. Published in Journal of Parallel and Distributed Computing, Vol. 8, February 1990, pp. 150-160.

  31. J.H. Reif and S. 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. [PostScript] [PDF] or [PostScript]

  32. J.H. Reif and S. Sen, Polling: A New Randomized Sampling Technique for Computational Geometry, 21st Annual ACM Symposium on Theory of Computing, Seattle, WA, May 1989, pp. 394-404. [PDF] Revised as Optimal Parallel Randomized Algorithms for Three-Dimensional Convex Hulls and Related Problems, Published in SIAM Journal on Computing, Vol. 21, No. 3, June 1992, pp. 466-485. [PDF] (see also Erratum: Optimal parallel randomized algorithms for three-dimensional convex hulls and related problems. SIAM Journal on Computing, 23(2):447-448, April 1994.)

  33. J.H. Reif and A. Tyagi, Energy Complexity of Optical Computations, 2nd IEEE Symposium on Parallel and Distributed Processing, Dallas, TX, December 1990, pp. 14-21. [PostScript] [PDF]

  34. E.S. Maniloff, K. Johnson, and J.H. Reif, Holographic Routing Network for Parallel Processing Machines Holographic Optics II: Principals and Applications, G. Michael Morris; Ed. SPIE Proceedings Series, Vol. 1136, EPS/EUROPTICA/SPIE International Congress on Optical Science and Engineering, Paris, France, April 1989, pp. 283-289.

  35. J.H. Reif, D. Tygar, and A. Yoshida, The Computability and Complexity of Optical Beam Tracing. 31st Annual IEEE Symposium on Foundations of Computer Science, St. Louis, MO, October 1990, pp. 106-114. Published as The Computability and Complexity of Ray Tracing in Discrete & Computational Geometry, 11: pp 265-287 (1994).

  36. S. Azhar, A. McLennan and J.H. Reif, Computation of Equilibria in Noncooperative Games, Duke University Technical Report CS-1991-36. Proc. Workshop for Computable Economics, Dec. 1992. [PostScript] [PDF]

  37. R. Paturi, S. Rajasekaran, and J.H. Reif, Efficient and Robust Learning Using Statistical Bootstrap, Workshop on Computational Learning Theory, Santa Cruz, CA, August 1989. [PostScript] [PDF] Published as The Light Bulb Problem, Information and Computation, 117(2):187-192, March 1995. [PDF]

  38. J.H. Reif and S. Sen, Randomized Parallel Algorithms. IBM Workshop on Capabilities and Limitations of Parallel Computing, San Jose, CA, December 1988. Information Processing 89, G. Ritter, ed., Elsevier Science Publishers, North Holland, 1989, pp. 455-458. Presented as Randomization in Parallel Algorithms and its Impact on Computational Geometry, in Optimal Algorithms;Lecture Notes in Computer Science, Vol. 401, 1989, pp. 1-8. Published as A Case for Randomized Parallel Algorithms in Opportunities and Constraints of Parallel Computing, J.L.C. Sanz (ed.), Springer-Verlag New York, 1989, pp. 101-105.

  39. V. Pan and J.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. 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]

  40. J.H. Reif and A. Tyagi, Efficient Algorithms for Optical Computing with the DFT Primitive, Presented at 10th Conference on Foundations of Software Technology and Theoretical Computer Science, Bangalore, India, December 1990; Lecture Notes in Computer Science. Published in Journal of Applied Optics, Vol. 36, 1997, pp. 7327-7341. [PDF] or [PostScript] [PDF]

  41. J. Canny, A. Rege, and J.H. Reif, An Exact Algorithm for Kinodynamic Planning in the Plane. 6th Annual ACM Symposium on Computational Geometry, Berkeley, CA, June 1990, pp. 271-280. [PDF] Published in Discrete and Computational Geometry, Vol. 6, 1991, pp. 461-484.

  42. J.H. Reif and S. Sen, Randomized Algorithms for Binary Search and Load Balancing on Fixed Connection Networks with Geometric Applications. 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, Crete, Greece, July 1990, pp. 327-337. Published in SIAM Journal of Computing 23:3, June, 1994, pp.633-651. [PDF]

  43. J.H. Reif, Efficient Parallel Algorithms: Theory and Practice. SIAM 35th Anniversary Meeting, Denver, CO, October 1987. XI World Computer Congress, IFIP 89, San Francisco, CA, 1989.

  44. H. Djidjev and J.H. Reif, An Efficient Algorithm for the Genus Problem with Explicit Construction of Forbidden Subgraphs. 23rd Annual ACM Symposium on Theory of Computing, New Orleans, LA, May 1991, pp. 337-347. [PDF]

  45. H. Gazit and J.H. Reif, A Randomized Parallel Algorithm for Planar Graph Isomorphism. 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, Crete, Greece, July 1990, pp. 210-219. Published in Journal of Algorithms, Vol. 28, No. 2, pp 290-314, August 1998. [PostScript] [PDF]

  46. V. Pan and J.H. Reif, The Parallel Computation of Minimum Cost Paths in Graphs by Stream Contraction, Information Processing Letters, Vol. 40, October 25,1991, pp. 79-83. [PDF]

  47. J.H. Reif and S. Tate, Approximate Kinodynamic Planning Using L2-norm Dynamic Bounds. Duke University Technical Report CS-1990-13, 1989. Published in Computers and Mathematics with Applications, Vol. 27, No.5, pp.29-44, March 1994. [PostScript] [PDF] or [PostScript]

  48. Royals, M., T. Markas, N. Kanopoulos, J.H. Reif and J. Storer, On the Design and Implementation of a Lossless Data Compression and Decompression Chip, IEEE Journal of Solid State Circuits (JSSC), Vol. 28, No. 9, pp. 948-953, Sep. 1993. [PDF]

  49. M. Karr, S. Krishnan, J.H. Reif, Derivation of the Ellipsoid Algorithm, Duke University Technical Report CS-1991-17, (1990).

  50. J.H. Reif and A. Tyagi, An Optical Delay Line Memory Model with Efficient Algorithms. Advanced Research in VLSI Conference, MIT Press, Santa Cruz, CA, March 1991. Published in Optical Engineering, 36(09), 2521-2535, Sept. (1997). [PostScript] [PDF]

  51. S. Azhar and J.H. Reif, Crypto-Complexity Based Models of Efficiency in Capital Markets, 1994.

  52. J.H. Reif and S. Tate, Continuous Alternation: The Complexity of Pursuit in Continuous Domains, Special Issue on Computational Robotics: the Geometric Theory of Manipulation, Planning and Control, Algorithmica, Vol. 10, pp. 151-181, 1993. [PostScript] [PDF] or [PostScript]

  53. J.H. Reif and A. Yoshida, Optical Expanders with Applications in Optical Computing, Journal of Applied Optics, 32, 1993, p.159-165. [PDF] or [PostScript] [PDF]

  54. J. A. Storer and J.H. Reif, Low-Cost Prevention of Error Propagation for Data Compression with Dynamic Dictionaries, Proceedings: IEEE Data Compression Conference (DCC'97) Snowbird, UT, IEEE Computer Society Press, James A. Storer, Martin Cohn (Eds.), March 1997, pp 171-180. Published as Error Resilient Optimal Data Compression, SICOMP, Vol 26, Num 4, July 1997, pp 934-939. [PostScript] [PDF]

  55. P.H. Mills, L.S. Nyland, J.F. Prins, J.H. Reif and R.A. Wagner, Prototyping Parallel and Distributed Programs in Proteus. 3rd IEEE Symposium on Parallel and Distributed Processing, Dallas, TX, pp. 10-19, IEEE, 1991. [PostScript] [PDF] or [Gzip.PostScript]

  56. J.A. Storer, T. Markas and J.H. Reif, A Massively Parallel VLSI Compression System using a Compact Dictionary. IEEE Workshops on VLSI & Signal Processing, 1990, San Diego, CA. Published as A Massively Parallel VLSI Compression System Using a Compact Dictionary, VLSI Signal Processing, No. 4, 1990 (edited by H.S. Moscovitz and K. Yao and R. Jain), IEEE Press, 1990, New York, NY, pp. 329-338.

  57. S. Krishan and J.H. Reif, Towards Randomized Strongly Polynomial Algorithms for Linear Programming, Duke University Technical Report CS-1991-18.

  58. V. Pan and J.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).

  59. T. Markas and J.H. Reif, Fast Computations of Vector Quantization Algorithms. NASA Technical Report TR-91-58, 1991.

  60. Tassos Markas and J.H. Reif, Image Compression Methods with Distortion Controlled Capabilities. IEEE Data Compression Conference (DCC 91), Snowbird, UT, IEEE Computer Society Press, April 1991, pp. 93-102. Published as Quad Tree Structures for Image Compression Applications, special issue of Journal of Information Processing and Management, 1992, pp. 707-721. [PDF]

  61. J. Cheriyan and J.H. Reif, Algebraic Methods for Testing the k-Vertex Connectivity of Directed Graphs, 3rd Annual ACM-SIAM Symposium on Discrete Algorithms, Orlando, Florida, 1992. [PDF] Published as "Directed s-t Numberings, Rubber Bands, and Testing Digraph k-Vertex Connectivity," in Combinatorica 14(4) 435-451, 1994.

  62. J.H. Reif and A. Yoshida, Optical Techniques for Image Compression. 2nd Annual IEEE Data Compression Conference (DCC 92), Snowbird, UT, IEEE Computer Society Press, James A. Storer, Martin Cohn (Eds.), March 1992, pp. 32-41. Also in Image and Text Compression, edited by J. A. Storer, Kluwer Academic Publishers, 1992. Published as "Optical Computing Techniques for Image/Video Compression," in Proceedings of the IEEE, 82:6, June 1994, pp. 948-954. [PDF]

  63. J.H. Reif and H. Wang, On Line Navigation Through Regions of Variable Densities. ARO Computational Geometry Workshop, Raleigh, North Carolina, October, 1993. Rewritten as On-Line Navigation Through Weighted Regions. [PostScript] [PDF] or [PostScript]

  64. M. Kao, J.H. Reif, and S. Tate, Searching in an Unknown Environment: An Optimal Randomized Algorithm for the Cow-Path Problem, Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'93), Austin, TX, Jan 1993, pp.441-447. Published in Information and Computation, Vol 131, No. 1 (1996), p 63-80. [PostScript] [PDF] or [PostScript]

  65. J.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. [PostScript] [PDF]

  66. J.H. Reif, An O(n log3 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]

  67. T. Markas and J.H. Reif, Memory-Shared Parallel Architectures for Vector Quantization Algorithms, 1992. Picture Coding Symposium, Lusanne Switzerland, March, 1993.

  68. P. Mills, L. Nyland, J. Prins, and J.H. Reif, Prototyping N-body Simulation in Proteus, Sixth International Parallel Processing Symposium, IEEE, Beverly Hills, CA, pp. 476-482, 1992. [PostScript] [PDF] or [PostScript]

  69. D. Armon and J.H. Reif, An Optimal Space and Efficient Parallel Nested Dissection Algorithm, 1992. 4th Annual ACM Symposium on Parallel Algorithms and Architectures, San Diego, CA, July 1992. [PDF]

  70. P. Mills, L. Nyland, J. Prins, and J.H. Reif, Prototyping High-Performance Parallel Computing Applications in Proteus. DARPA Software Technology Conference, May, 1992. [PostScript] [PDF]

  71. V. Pan, J.H. Reif, S. Tate. The Power of Combining the Techniques of Algebraic and Numerical Computing: Improved Approximate Multipoint Polynomial Evaluation and Improved Multipole Algorithms, 32th Annual IEEE Symposium on Foundations of Computer Science (FOCS'92), Pittsburgh, PA, Oct. 1992, pp. 703-713. Rewritten as J.H. Reif and S. Tate, "N-body simulation I: Fast algorithms for potential field evaluation and Trummer's problem". Tech. Report. #N-96-002, Univ. of North Texas, Dept. of Computer Science (1996). [PostScript] [PDF]

  72. W.L. Hightower, J. Prins, and J.H. Reif, Implementations of Randomized Sorting on Large Parallel Machines. 4th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA'92), San Diego, CA, July 1992. [PDF]

  73. Y. Han, V. Pan, and J.H. Reif, Efficient Parallel Algorithms for Computing All Pair Shortest Paths in Directed Graphs. University of Kentucky Technical Report 204-92. 4th Annual ACM Symposium on Parallel Algorithms and Architectures, San Diego, CA, July 1992, pp. 353-362. Published in Algorithmica, Vol 17, pp. 399-415, 1997. [PDF]

  74. J.H. Reif and H. Wang, Social Potential Fields: A Distributed Behavioral Control for Autonomous Robots, Workshop on Algorithmic Foundations of Robotics (WAFR'94), San Francisco, California, February, 1994; The Algorithmic Foundations of Robotics, A.K.Peters, Boston, MA. 1995. Published in Robotics and Autonomous Systems, Vol. 27, no.3, pp.171-194, (May 1999). [PostScript] [PDF]

  75. J.H. Reif and S. 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]

  76. J.H. Reif and S. R. Tate, Dynamic Parallel Tree Contraction, 5th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA'94), Cape May, NJ, June 1994. pp.114-121. [PostScript] [PDF] or [PostScript]

  77. D. Armon and J.H. Reif, A Dynamic Separator Algorithm with Applications to Computational Geometry and Nested Dissection, 3rd Annual Workshop on Algorithms and Data Structures (WADS '93), Montreal, Quebec, Canada, August, 1993, p.107-118. [PDF]

  78. S. Azhar, G. Badros, A. Glodjo, M. Kao, and J.H. Reif, Data Compression Techniques for Stock Market Prediction, Proceedings: IEEE Data Compression Conference (DCC'94), Snowbird, UT, IEEE Computer Society Press, James A. Storer, Martin Cohn (Eds.), March 1994, p. 72-82. [PDF]

  79. J. Cheriyan and J.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 J.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]

  80. S. Nikoletseas, J.H. Reif, P.G. Spirakis, and M. Yung, Stochastic Graphs Have Short Memory: Fully Dynamic Connectivity in Poly-Log Expected Time. Proceedings of the 22nd Annual Colloquium on Automata, Languages and Programming (ICALP'93), Szeged, Hungary, July 1993. [PostScript] [PDF]

  81. S.R. Tate and J.H. Reif, The Complexity of N-body Simulation, Proceedings of the 20th Annual Colloquium on Automata, Languages and Programming (ICALP'93), Lund, Sweden, July, 1993, p. 162-176. [PostScript] [PDF] or [PostScript]

  82. Tassos Markas and J.H. Reif, Multispectral Image Compression Algorithms, Proceedings: IEEE Data Compression Conference (DCC'93), Snowbird, UT, IEEE Computer Society Press, James A. Storer, Martin Cohn (Eds.), p.391-400, March 1993. [PDF]

  83. P. Mills, J. Prins, and J.H. Reif, Rate Control as a Language Construct for Parallel and Distributed Programming, Proc. IEEE Workshop on Parallel and Distributed Real-Time Systems (IPPS'93), pp. 164-170, 1993. [PostScript] [PDF]

  84. R. Barakat and J.H. Reif, Diffraction Realization of an Optical Expander, (1993).

  85. L. S. Nyland, J. F. Prins, and J.H. Reif, A Data Parallel Implementation of the Adaptive Fast Multipole Algorithm. Dartmouth Institute for Advanced Graduate Studies (DAGS '93), Hanover, NH, June, 1993. [PostScript] [PDF]

  86. S. Chen and J.H. Reif, Using Difficulty of Prediction to Decrease Computation: Fast Sort, Priority Queue and Convex Hull on Entropy Bounded Inputs, 34th Annual IEEE Conference on Foundations of Computer Science (FOCS '93) Proceedings, November 1993, Palo Alto, CA, pp. 104-112. [PDF]

  87. Neff, A. and J.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):81-115, (June 1996). [PostScript] [PDF]

  88. A. Goldberg, J. Prins, R. Faith, Z. Li, P. Mills, L. Nyland, D. Palmer, J.H. Reif, J. Riely, and S. Westfold, The Proteus System for the Development of Parallel Applications. Prototyping and Software Development (M.C.~Harrison, ed.), Lecture Notes in Computer Science, pp.~151--190, Springer-Verlag, 1996. [PostScript] [PDF]

  89. P.H. Mills, L.S. Nyland, J.F. Prins, and J.H. Reif, Software Issues in High-Performance Computing and a Framework for the Development of HPC Applications,Developing a Computer Science Agenda for High Performance Computing (U. Vishkin, ed.) pp.110-117, ACM, 1994. [PostScript] [PDF]

  90. A. Goldberg, P. H. Mills, L. S. Nyland, J. F. Prins, J.H. Reif, and J. Riely, Specification and Development of Parallel Algorithms with the Proteus System, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, AMS Press, Vol.

    Download 157.8 Kb.

    Share with your friends:
  1   2



The database is protected by copyright ©ininet.org 2024
send message
    Main page
mathematical theory
fourth workshop