List of Publications, Uzi Vishkin


ARTICLES IN JOURNALS

  1. Y. Shiloach and U. Vishkin. Finding the maximum, merging and sorting in a parallel computation model. J. of Algorithms, 2 (1981), 88-102.
  2. Y. Shiloach and U. Vishkin. An O(log n) parallel connectivity algorithm. J. of Algorithms, 3 (1982), 57-67.
  3. R. Bar-Yehuda and U. Vishkin. Complexity of finding k path-free dominating sets in graphs. Information Processing Letters, 14, 5 (1982), 228-232.
  4. U. Vishkin. An efficient distributed orientation algorithm. IEEE Trans. on Information Theory IT-29, 4 (July 1983), 624-629.
  5. Y. Shiloach, U. Vishkin and S. Zaks. Golden ratios in pair covering problems. Discrete Mathematics, 41 (1982), 57-65.
  6. Y. Shiloach and U. Vishkin. An O((n**2)log n) parallel max-flow algorithm. J. of Algorithms, 3 (1982), 128-146.
  7. U. Vishkin. Implementation of simultaneous memory address access in models that forbid it. J. of Algorithms, 4 (March 1983), 45-50.
  8. W. Paul, U. Vishkin and H. Wagener. Parallel computation on 2-3 trees. RAIRO-Theoretical Informatics 17,4 (1983), 397-404.
  9. U. Vishkin and A. Wigderson. Dynamic parallel memories. Information and Control 56,3 (1983), 174-182.
  10. L.J. Stockmeyer and U. Vishkin. Simulation of parallel random access machines by circuits. SIAM J. Computing 13,2 (1984), 409-422.
  11. A.K. Chandra, L.J. Stockmeyer and U. Vishkin. Constant depth reducibility. SIAM J. Computing 13,2 (1984), 423-439.
  12. Y. Gurevich, L. J. Stockmeyer and U. Vishkin. Solving NP-hard problems on graphs that are almost trees with applications to facility location problems. J. of ACM 31,3 (1984), 459-473.
  13. U. Vishkin. An optimal parallel connectivity algorithm. Discrete Applied Mathematics 9 (1984), 197-207.
  14. U. Vishkin. Parallel-Design Distributed-Implementation (PDDI) General Purpose Computer. Theoretical Computer Science 32 (1984), 157-172.
  15. K. Mehlhorn and U. Vishkin. Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories. Acta Informatica 21 (1984), 339-374.
  16. M.J. Atallah and U. Vishkin. Finding Euler tours in parallel. J. of Computer Systems and Sciences 29, 3 (1984), 330-337.
  17. D. Coppersmith and U. Vishkin. Solving NP-hard problems on 'almost trees': Vertex Cover. Discrete Applied Mathematics 10 (1985), 27-45.
  18. U. Vishkin and A. Wigderson. Trade-offs between depth and width in parallel computation. SIAM J. Computing 14,2 (1985), 303-314.
  19. I. Bar-On and U. Vishkin. Optimal parallel generation of a computation tree form. ACM Tran. on Prog. Lang. and Sys. 7,2 (1985), 348-357.
  20. U. Vishkin. On efficient parallel strong orientation. Information Processing Letters 20 (1985), 235-240.
  21. Y. Perl and U. Vishkin. Efficient implementation of a shifting algorithm. Discrete Applied Mathematics 12,1 (1985), 71-80.
  22. R.E. Tarjan and U. Vishkin. An efficient parallel biconnectivity algorithm. SIAM J. Computing 14,4 (1985), 862-874.
  23. G.M Landau, U. Vishkin and R. Nussinov. An efficient string matching algorithm with k differences for nucleotide and amino acid sequences. Nucleic Acids Research (Computer Issue) 14,1 (1986), 31-46.
  24. U. Vishkin. Optimal parallel pattern matching in strings. Information and Control 67,1-3 (1985), 91-113.
  25. G.M. Landau and U. Vishkin. Efficient string matching with k mismatches. Theoretical Computer Science 43 (1986), 239-249.
  26. R. Cole and U. Vishkin. Deterministic coin tossing with applications to optimal parallel list ranking. Information and Control 70 (1986), 32-53.
  27. U. Vishkin. An optimal parallel algorithm for selection. Advances in Computing Research 4 (Special Issue on Parallel and Distributed Computing) (1987), 79-86.
  28. Y. Maon, B. Schieber and U. Vishkin. Parallel ear decomposition search (EDS) and st-numbering in graphs. Theoretical Computer Science 47 (1986), 277-298.
  29. Y. Azar and U. Vishkin. Tight comparison bounds on the complexity of parallel sorting. SIAM J. Computing 16,3 (1987), 458-464.
  30. U. Vishkin. Randomized parallel speed-ups for list ranking. J. of Parallel and Distributed Computing 4,3 (1987), 319-333.
  31. G.M. Landau, U. Vishkin and R. Nussinov. An efficient string matching algorithm with k substitutions for nucleotides and amino acid sequences. J. of Theoretical Biology 126 (1987), 483-490.
  32. G.M Landau, U. Vishkin and R. Nussinov. Locating alignments with k differences for nucleotide and amino acid sequences. Computer Applications in the Biosciences (CABIOS) 4,1 (1988), 19-24. Joint issue with Nucleic Acids Research.
  33. R. Cole and U. Vishkin. The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time. Algorithmica 3 (1988), 329-346, special issue on Parallel and Distributed Computing.
  34. A. Apostolico, C. Iliopoulos, G.M. Landau, B. Schieber and U. Vishkin. Parallel construction of a suffix tree with applications. Algorithmica 3 (1988), 347-365, special issue on Parallel and Distributed Computing.
  35. R. Cole and U. Vishkin. Approximate parallel scheduling. Part I: The basic technique with applications to optimal parallel list ranking in logarithmic time. SIAM J. Computing 17 (1988), 128-142.
  36. G.M. Landau and U. Vishkin. Fast string matching with k differences. J. of Computer Systems and Sciences (special issue of selected papers from FOCS 1985) 37,1 (1988), 63-78.
  37. B. Schieber and U. Vishkin. On finding lowest common ancestors: simplification and parallelization. SIAM J. Computing 17,6 (1988), 1253-1262.
  38. N. Megiddo and U. Vishkin. On finding a minimum dominating set in a tournament. Theoretical Computer Science 61, 2-3 (1988), 307-316.
  39. T. Tzoreff-Eilam and U. Vishkin. Matching patterns in strings subject to multi-linear transformations. Theoretical Computer Science 60 (Special volume on Fundamental Studies),3 (1988), 231-254.
  40. G.M. Landau and U. Vishkin. Fast parallel and serial approximate string matching. J. of Algorithms 10 (1989), 157-169.
  41. R. Cole and U. Vishkin. Faster optimal prefix sums and list ranking. Information and Computation 81 (1989), 334-352.
  42. G.M. Landau, U. Vishkin and R. Nussinov. Fast alignment of DNA and protein sequences. Methods in Enzymology (a volume on Molecular Evolution: Computer Analysis of Protein and Nucleic Acid Sequences) 183, 1990, 487-502.
  43. B. Schieber and U. Vishkin. Finding all nearest neighbors for convex polygons in parallel: a new lower bound technique and a matching algorithm. Discrete Applied Mathematics (Special Issue on Parallel Complexity Using Combinatorics), 29 (1990), 97-111.
  44. U. Vishkin. Deterministic sampling - a new technique for fast pattern matching. SIAM J. Computing, 20,1 (1991), 22-40.
  45. R. Cole and U. Vishkin. Approximate parallel scheduling. II. Applications to optimal parallel graph algorithms in logarithmic time. Information and Computation 91,1 (1991), 1-47.
  46. Y. Matias and U. Vishkin. On parallel hashing and integer sorting. J. of Algorithms 12,4 (1991) 573-606.
  47. A. Amir, G.M. Landau and U. Vishkin. Efficient pattern matching with scaling. J. of Algorithms (Special Issue of Papers Selected from 1st ACM-SIAM Symp. on Discrete Algorithms) 13,1 (1992) 2-32.
  48. U. Vishkin. A parallel blocking flow algorithm for acyclic networks. J. of Algorithms 13,3 (1992) 489-501.
  49. O. Berkman and U. Vishkin. Recursive star-tree parallel data-structure. SIAM J. Computing 22,2 (1993) 221-242.
  50. O. Berkman, B. Schieber and U. Vishkin. Optimal doubly logarithmic optimal parallel algorithms based on finding all nearest smaller values. J. of Algorithms 14 (1993) 344-370.
  51. O. Berkman, Y. Matias and U. Vishkin. Randomized Range-Maxima in Nearly-Constant Parallel Time. Computational Complexity 2 (1992) 350-373.
  52. O. Berkman and U. Vishkin. On parallel integer merging. Information and Computation 106 (1993), 266-285.
  53. S. Khuller and U. Vishkin. Biconnectivity approximations and graph carvings. JACM 41,2 (1994), 214-235.
  54. O. Berkman, J. JaJa, S. Krishnamurthy, R. Thurimella and U. Vishkin. Top-bottom routing around a rectangle is as easy as computing prefix minima. SIAM J. Computing 23,3 (1994), 449-465.
  55. O. Berkman and U. Vishkin. Finding level-ancestors in trees. J. of Computer Systems and Sciences 48,2 (1994), 214-230.
  56. R. Cole and U. Vishkin. On the detection of robust curves. Computer Vision, Graphics, and Image Processing (CVGIP): Graphical Models and Image Processing 56,3 (1994), 189-204.
  57. G.M. Landau and U. Vishkin. Pattern matching in a digitized image. Algorithmica, 12,4/5 (1994), 375-408.
  58. S. Khuller, U. Vishkin and N. Young. A primal-dual parallel approximation technique applied to weighted set and vertex cover. J. Algorithms, 17,2 (1994), 280-289.
  59. S. Khuller and U. Vishkin. On the parallel complexity of digraph reachability. Information Processing Letters, 52,5 (1994), 239-242.
  60. O. Berkman and U. Vishkin. Almost fully-parallel parentheses matching. Discrete Applied Mathematics, 57 (1995), 11-28.
  61. J. JaJa, K.W. Ryu, and U. Vishkin. Sorting strings and constructing search trees in parallel. Theoretical Computer Science, 154,2 (1996), 225-245.
  62. O. Berkman, B. Schieber and U. Vishkin. A fast parallel algorithm for finding the convex hull of a sorted point set. International Journal of Computational Geometry and Applications, 6 (1996), 231-241.
  63. U. Vishkin. Can parallel algorithms enhance serial implementation? Communications of the ACM, 39,9 (1996), 88-91.

  • Please see the Explicit Multi-Threading (XMT) home page for more recent papers.

    BOOK CHAPTERS

    1. U. Vishkin. Advanced Parallel Prefix-sums, List Ranking and Connectivity. In Synthesis of Parallel Algorithms (Editor: John H. Reif), Morgan-Kaufmann, 1993, 215-258.
    2. U. Vishkin. Structural parallel algorithmics. In Lectures on Parallel Computation, Editors: Alan Gibbons and Paul Spirakis, Cambridge University Press, 1993, 1-18.
    3. G.M. Landau and U. Vishkin. Approximate string matching. In Pattern Matching Algorithms, Editors: Alberto Apostolico and Zvi Galil, Oxford University Press, 1997, 185-199.

    BOOK

    1. U. Vishkin (editor), Developing a Computer Science Agenda for High-Performance Computing, ACM Press, 1994, 158 pages.

    ARTICLES IN PROCEEDINGS OF CONFERENCES

    1. Y. Shiloach and U. Vishkin. Finding the maximum, merging and sorting in a parallel computation model. In Proc. Conference of Analyzing Problem Classes and Programming for Parallel Computing, CONPAR 81, Nurnberg, F.R. Germany, Lecture Notes in Computer Science, Vol. 111, Springer- verlag, 1981, 314-327.
    2. A.K. Chandra, L.J. Stockmeyer and U. Vishkin. A complexity theory for unbounded fan-in parallelism. In Proc. 23rd Annual IEEE Symposium on Foundations of Computer Science, 1982, 1-13.
    3. W. Paul, U. Vishkin and H. Wagener. Parallel dictionaries on 2-3 trees. In Proc. 10th ICALP, Lecture Notes in Computer Science, Vol. 154, Springer-Verlag, 1983, 597-609.
    4. U. Vishkin and A. Wigderson. Trade-offs between depth and width in parallel computation. In Proc. 24th Annual IEEE Symposium on Foundations of Computer Science, 1983, 146-153.
    5. U. Vishkin. Randomized speed-ups in parallel computation. In Proc. 16th Annual ACM Symp. on Theory of Computing, 1984, 230-239.
    6. I. Bar-On and U. Vishkin. Optimal parallel generation of a computation tree form. In Proc. 13th Annual International Conference on Parallel Processing, 1984, 490-495.
    7. K. Mehlhorn and U. Vishkin. Granularity of memory in parallel computation. In Proc. 9th Workshop on Graphtheoretic Concepts in Computer Science (WG-83), Fachbereich Mathematik, Universitat Osnabruck, June 1983.
    8. R.E. Tarjan and U. Vishkin. Finding biconnected components and computing tree functions in logarithmic parallel time. In Proc. 25th Annual IEEE Symposium on Foundations of Computer Science, 1984, 12-20.
    9. U. Vishkin. Optimal parallel pattern matching in strings. In Proc. 12th ICALP, Lecture Note in Computer Science, Vol. 194, Springer-Verlag, 1985, 497-508.
    10. G.M Landau and U. Vishkin. Efficient string matching in the presence of errors. In Proc. 26th Annual IEEE Symposium on Foundations of Computer Science, 1985, 126-136.
    11. R. Cole and U. Vishkin. Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms. In Proc. 18th Annual ACM Symp. on Theory of Computing, 1986, 206-219.
    12. G.M. Landau and U. Vishkin. Introducing efficient parallelism into approximate string matching and a new serial algorithm. In Proc. 18th Annual ACM Symp. on Theory of Computing, 1986, 220-230.
    13. R. Cole and U. Vishkin. Approximate and exact parallel scheduling with applications for list, tree and graph algorithms. In Proc. 27th Annual IEEE Symposium on Foundations of Computer Science, 1986, 478-491.
    14. N. Alon, Y. Azar and U. Vishkin. Tight complexity bounds for parallel comparison sorting. In Proc. 27th Annual IEEE Symposium on Foundations of Computer Science, 1986, 502-510.
    15. Y. Maon, B. Schieber and U. Vishkin. Parallel ear decomposition search (EDS) and st-numbering in graphs. In AWOC 86: Proc. 2nd International Workshop on Parallel Computing and VLSI, Lecture Notes in Computer Science, Vol. 227, Springer-Verlag, 1986, 34-45.
    16. G.M. Landau, B. Schieber and U. Vishkin. Parallel construction of a suffix tree. In Proc. 14th ICALP, Lecture Notes in Computer Science, Vol. 267 Springer-Verlag, 1987, 314-325.
    17. V.L. Ramachandran and U. Vishkin. Efficient parallel triconnectivity in logarithmic parallel time. In AWOC 88: Third International Workshop on Parallel Computation and VLSI Theory, Corfu Island, Greece, June 28 - July 1, 1988. Lecture Notes in Computer Science, Vol. 319, Springer-Verlag, 33-42.
    18. B. Schieber and U. Vishkin. On finding lowest common ancestors: simplification and parallelization. In AWOC 88: Third International Workshop on Parallel Computation and VLSI Theory, Corfu Island, Greece, June 28 - July 1, 1988. Lecture Notes in Computer Science, Vol. 319, Springer-Verlag, 111-123.
    19. R. Cole and U. Vishkin. Optimal parallel algorithms for expression tree evaluation and list ranking. In AWOC 88: Third International Workshop on Parallel Computation and VLSI Theory, Corfu Island, Greece, June 28 - July 1, 1988. Lecture Notes in Computer Science, Vol. 319, Springer-Verlag, 91-100.
    20. T. Tzoreff-Eilam and U. Vishkin. Matching patterns in strings subject to multi-linear transformations In Sequences: Combinatorics, Compression, Security and Transmission, (ed. R.M. Capocelli), Springer-verlag, 1990, 45-58. Workshop was held in Amalfi Coast, Salerno, Italy, on June 6-10, 1988.
    21. O. Berkman, D. Breslauer, Z. Galil, B. Schieber and U. Vishkin. Highly parallelizable problems. In Proc. 21st Annual ACM Symp. on Theory of Computing, 1989, 309-319.
    22. O. Berkman and U. Vishkin. Recursive *-tree parallel data-structure. In Proc. 30th Annual IEEE Symposium on Foundations of Computer Science, 1989, 196-202.
    23. A. Amir, G.M. Landau and U. Vishkin. Efficient pattern matching with scaling. In Proc. First Annual ACM-SIAM Symp. on Discrete Algorithms, 1990, 344-357.
    24. U. Vishkin. Deterministic sampling - a new technique for fast pattern matching. In Proc. 22nd Annual ACM Symp. on Theory of Computing, 1990, 170-180.
    25. Y. Matias and U. Vishkin. On integer sorting and parallel hashing. In Proc. 17th ICALP, Lecture Notes in Computer Science, Vol. 443, Springer-Verlag, 1990, 729-743.
    26. O. Berkman, J. JaJa, S. Krishnamurthy, R. Thurimella and U. Vishkin. Some triply-logarithmic parallel algorithms. In Proc. 31st Annual IEEE Symposium on Foundations of Computer Science, 1990, 871-881.
    27. Y. Matias and U. Vishkin. Converting high probability into nearly-constant time - with applications to parallel hashing. In Proc. 23rd Annual ACM Symp. on Theory of Computing, 1991, 307-316.
    28. U. Vishkin. Structural parallel algorithmics. In Proc. 18th ICALP, Lecture Notes in Computer Science, Vol. 510 Springer-Verlag, 1991, 363-380.
    29. J. Gil, Y. Matias and U. Vishkin. Towards a theory of nearly constant time parallel algorithms. In Proc. 32nd Annual IEEE Symposium on Foundations of Computer Science, 1991, 698-710.
    30. G.M. Landau and U. Vishkin. Pattern matching in a digitized image. In Proc. Third Annual ACM-SIAM Symp. on Discrete Algorithms, 1992, 453-462.
    31. S. Khuller and U. Vishkin. Biconnectivity approximations and graph carvings. In Proc. 24th Annual ACM Symp. on Theory of Computing, 1992, 759-770.
    32. U. Vishkin. Methods in parallel algorithmics and who may need to know them? In Proc. Third annual International Symposium on Algorithms and Computation (ISAAC'92), Lecture Notes in Computer Science, Springer-Verlag, Vol. 650, 1992, 1-4.
    33. O. Berkman, Y. Matias and U. Vishkin. Randomized Range-Maxima in Nearly-Constant Parallel Time. In Proc. Third annual International Symposium on Algorithms and Computation (ISAAC'92), Lecture Notes in Computer Science, Vol. 650, Springer-Verlag, 1992, 135-144.
    34. U. Vishkin. A case for the PRAM as a standard programmer's model. In Proc. Workshop on Parallel Architectures and Their Efficient Use: State of the Art and Perspectives, First Heinz-Nixdorf Symposium, Paderborn, Germany, November 11 - 13, 1992, Lecture Notes in Computer Science, Volume 678, 1993, 11-19.
    35. S. Khuller, U. Vishkin and N. Young. A primal-dual parallel approximation technique applied to weighted set and vertex cover. In Proc. 3rd Integer Programming and Combinatorial Optimization (IPCO) Conference, 1993, 333-341.
    36. G.M. Landau and U. Vishkin. Two dimensional pattern matching in a digitized image. In Proc. Fourth Conference on Combinatorial Pattern Matching, Lecture Notes in Computer Science, Vol. 684, Springer-Verlag, 1993, 134-151.
    37. M.T. Goodrich, Y. Matias and U. Vishkin. Approximate parallel prefix computation and its Applications. In Proc. 7th IEEE International Parallel Processing Symposium (IPPS), 1993, 318-325.
    38. R. Raman and U. Vishkin. Optimal parallel algorithms for totally monotone matrix searching. In Proc. Fifth Annual ACM-SIAM Symp. on Discrete Algorithms, 1994, 613-621.
    39. M.T. Goodrich, Y. Matias and U. Vishkin. Optimal parallel approximation algorithms for prefix sums and integer sorting. In Proc. Fifth Annual ACM-SIAM Symp. on Discrete Algorithms, 1994, 241-250.
    40. J. JaJa, K.W. Ryu, and U. Vishkin. Sorting strings and constructing search trees in parallel. In Proc. 8th IEEE International Parallel Processing Symposium (IPPS), 1994, 349-356.
    41. U. Vishkin. Can parallel algorithms enhance serial implementation? In Proc. 8th IEEE International Parallel Processing Symposium (IPPS), 1994, 376-385.
    42. S. C. Sahinalp and U. Vishkin. Symmetry breaking for suffix tree construction. In Proc. 26th Annual ACM Symp. on Theory of Computing, 1994, 300-309.
    43. Y. Mansour, N. Nisan, and U. Vishkin. Trade-offs between communication throughput and parallel time. In Proc. 26th Annual ACM Symp. on Theory of Computing, 1994, 372-381.
    44. S. C. Sahinalp and U. Vishkin. On a parallel-algorithms method for string matching problems. In The second Italian Conference on Algorithms and Complexity, Rome, Italy, Lecture Notes in Computer Science, Vol. 778, Springer-verlag, 1994, 22-32.
    45. Y. Matias and U. Vishkin. A note on reducing parallel model simulations to integer sorting. In Proc. 9th IEEE International Parallel Processing Symposium (IPPS), 1995.
    46. R. Raman and U. Vishkin. Parallel algorithms for database operations and a database operation for parallel algorithms. In Proc. 9th IEEE International Parallel Processing Symposium (IPPS), 1995.
    47. S. C. Sahinalp and U. Vishkin. Efficient approximate and dynamic matching of patterns using a labeling paradigm. In Proc. 37th Annual IEEE Symposium on Foundations of Computer Science, 1996.
    48. S.M. Mueller and U. Vishkin. Conflict-Free Access to Multiple Single-Ported Register Files. In Proc. 11th IEEE International Parallel Processing Symposium (IPPS), 1997.
    49. U. Vishkin. From algorithm parallelism to instruction-level parallelism: an encode-decode chain using prefix-sum. In Proc. 9th ACM Symposium on Parallel Algorithms and Architectures (SPAA), 1997.
    50. U. Vishkin, S. Dascal, E. Berkovich and J. Nuzman. Explicit Multi-Threading (XMT) Bridging Models for Instruction Parallelism. In Proc. 10th ACM Symposium on Parallel Algorithms and Architectures (SPAA), 1998.
  • Please see the Explicit Multi-Threading (XMT) home page for more recent papers.

    THESES

    1. U. Vishkin. Information in Economics. M.Sc. Thesis, Department of Mathematics, Hebrew University, Jerusalem, Israel, 1975. Advisor: Prof. R.J. Aumann.
    2. U. Vishkin. Synchronized Parallel Computation. D.Sc. Thesis, Computer Science Department, Technion, Haifa, Israel, 1981. Main results appear in journal articles 1,2 and 6. Advisor: Prof. Y. Shiloach.

    OTHER ARTICLES

    1. U. Vishkin. Synchronous parallel computation - a survey. TR 71, Department of Computer Science, Courant Institute, New York University, 1983. The paper also appeared (by their invitation) at the annual paper collection of "Datalogforeningen" (The Computer Science Association of Aarhus, Denmark), 1987, 76-89. The theme of the 1987 volume is "parallelism" and it included eleven papers.
    2. U. Vishkin. On choice of a parallel model of computation. TR-61, Dept. of Computer Science, Courant Institute, New York University, 1983.
    3. U. Vishkin. Project for developing computer science agenda(s) for high-performance computing: an organizer's summary. UMIACS-TR-94-129, University of Maryland Institute for Advanced Computer Studies, College Park, MD 20742-3251, November 1994.
    4. R. Orny and U. Vishkin. Two computer systems paradoxes: serialize-to-parallelize, and queuing concurrent-writes, UMIACS-TR-96-1, University of Maryland Institute for Advanced Computer Studies, College Park, MD 20742-3251, September 1995.

    Fri Jan 3 12:12:11 EST 1997