Uzi Vishkin

Professor
5216 Iribe Center
(301) 405-6763
Academic Web Page
Education: 
D.Sc., Technion - Israel Institute of Technology (Computer Science)
Special Awards/Honors: 
ACM Fellow
Biography: 

Uzi Vishkin is a professor of electrical and computer engineering with an appointment in the University of Maryland Institute for Advanced Computer Studies.

His research focuses on aligning the theory of parallel algorithms, parallel programming, and many-core hardware into a cohesive computing stack for future processors. Vishkin has developed a unique approach that enables single-threaded programming for parallelism to achieve competitive many-core performance, directly harnessing the theory of parallel algorithms.

Go here to view Vishkin's academic publications on Google Scholar.

Publications

1994


Sahinalp SC, Vishkin U.  1994.  On a parallel-algorithms method for string matching problems. Lecture Notes in Computer Science. 778:22-32.

Khuller S, Vishkin U.  1994.  On the parallel complexity of digraph reachability. Information Processing Letters. 52(5):239-241.

Raman R, Vishkin U.  1994.  Optimal randomized parallel algorithms for computing the row maxima of a totally monotone matrix. Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms. :613-621.

Mansour Y, Nisan N, Vishkin U.  1994.  Trade-offs between communication throughput and parallel time. Proceedings of the twenty-sixth annual ACM symposium on Theory of computing. :372-381.

[Anonymous].  1994.  Developing a computer science agenda for high-performance computing.

Landau GM, Vishkin U.  1994.  Pattern matching in a digitized image. Algorithmica. 12(4):375-408.

Goodrich MT, Matias Y, Vishkin U.  1994.  Optimal parallel approximation for prefix sums and integer sorting. Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms. :241-250.

Cole R, Vishkin U.  1994.  On the detection of robust curves. CVGIP: Graphical Models and Image Processing. 56(3):189-204.

Berkman O, Vishkin U.  1994.  Finding level-ancestors in trees. Journal of Computer and System Sciences. 48(2):214-230.

1993


Berkman O, Vishkin U.  1993.  On parallel integer merging. Information and Computation. 106(2):266-285.

Berkman O, Schieber B, Vishkin U.  1993.  Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values. Journal of Algorithms. 14(3):344-370.

Vishkin U.  1993.  Advanced parallel prefix-sums, list ranking and connectivity. Synthesis of Parallel Algorithms. :215-257.

Vishkin U.  1993.  A case for the PRAM as a standard programmer's model. Parallel Architectures and their Efficient Use. :11-19.

Landau G, Vishkin U.  1993.  Two dimensional pattern matching in a digitized image. Combinatorial Pattern Matching. :134-151.

Goodrich MT, Matias Y, Vishkin U.  1993.  Approximate parallel prefix computation and its applications. Parallel Processing Symposium, 1993., Proceedings of Seventh International. :318-325.

1992


Vishkin U.  1992.  A parallel blocking flow algorithm for acyclic networks. Journal of Algorithms. 13(3):489-501.

Vishkin U.  1992.  Biconnectivity Approximations and Graph Carvings. Proceedings of the Twenty-fourth Annual ACM Symposium on the Theory of Computing, Victoria, British Columbia, Canada, May 4-6, 1992. :759-759.

Vishkin U.  1992.  Methods in parallel algorithmics and who may need to know them? Algorithms and Computation. :1-4.

Vishkin U.  1992.  Methods in parallel algorithmcs. Mathematical Foundations of Computer Science 1992. :81-81.

Berkman O, Matias Y, Vishkin U.  1992.  Randomized range-maxima in nearly-constant parallel time. Computational Complexity. 2(4):350-373.

Amir A, Landau GM, Vishkin U.  1992.  Efficient pattern matching with scaling. Journal of Algorithms. 13(1):2-32.

1991


Gil J, Matias Y, Vishkin U.  1991.  Towards a theory of nearly constant time parallel algorithms. Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on. :698-710.

Vishkin U.  1991.  Can parallel algorithms enhance serial implementation? Parallel Processing Symposium, 1994. Proceedings., Eighth International. :376-385.

Vishkin U.  1991.  Structural parallel algorithmics. Automata, Languages and Programming. :363-380.

Matias Y, Vishkin U.  1991.  Converting high probability into nearly-constant time—with applications to parallel hashing. Proceedings of the twenty-third annual ACM symposium on Theory of computing. :307-316.

Matias Y, Vishkin U.  1991.  On parallel hashing and integer sorting. Journal of Algorithms. 12(4):573-606.

Cole R, Vishkin U.  1991.  Approximate parallel scheduling. II. Applications to logarithmic-time optimal parallel graph algorithms. Information and Computation. 92(1):1-47.

1990


Landau GM, Vishkin U, Nussinov R.  1990.  Fast alignment of DNA and protein sequences. Methods in enzymology. 183:487-502.

Vishkin U.  1990.  Deterministic sampling—a new technique for fast pattern matching. Proceedings of the twenty-second annual ACM symposium on Theory of computing. :170-180.

Schieber B, Vishkin U.  1990.  Finding all nearest neighbors for convex polygons in parallel: a new lower bound technique and a matching algorithm. Discrete Applied Mathematics. 29(1):97-111.

Landau GM, Vishkin U, Nussinov R.  1990.  [31] Fast alignment of DNA and protein sequences. Methods in Enzymology. 183:487-502.

1989


Landau GM, Vishkin U.  1989.  Fast parallel and serial approximate string matching* 1. Journal of Algorithms. 10(2):157-169.

Cole R, Vishkin U.  1989.  Faster optimal parallel prefix sums and list ranking. Information and Computation. 81(3):334-352.

1988


Vishkin U.  1988.  PRAM algorithms: teach and preach. collection of position papers, IBM-NSF Workshop on$\textbackslashbackslash$ Opportunities and Constraints of Parallel Computing", IBM Almaden.

Schieber B, Vishkin U.  1988.  On finding lowest common ancestors: simplification and parallelization. VLSI Algorithms and Architectures. :111-123.

Ramachandran V, Vishkin U.  1988.  Efficient parallel triconnectivity in logarithmic time. VLSI Algorithms and Architectures. :33-42.

Megiddo N, Vishkin U.  1988.  On finding a minimum dominating set in a tournament. Theoretical Computer Science. 61(2-3):307-316.

Landau GM, Vishkin U, Nussinov R.  1988.  Locating alignments with k differences for nucleotide and amino acid sequences. Computer applications in the biosciences: CABIOS. 4(1):19-19.

Landau GM, Vishkin U.  1988.  Fast string matching with k differences.. J. COMP. SYST. SCI.. 37(1):63-78.

Landau GM, Vishkin U.  1988.  Fast string matching with k differences* 1,* 2. Journal of Computer and System Sciences. 37(1):63-78.

Eilam-Tzoreff T, Vishkin U.  1988.  Matching patterns in strings subject to multi-linear transformations. Theoretical Computer Science. 60(3):231-254.

Cole R, Vishkin U.  1988.  Approximate parallel scheduling. Part I: The basic technique with applications to optimal parallel list ranking in logarithmic time. SIAM Journal on Computing. 17:128-128.

Cole R, Vishkin U.  1988.  Optimal parallel algorithms for expression tree evaluation and list ranking. VLSI Algorithms and Architectures. :91-100.

Cole R, Vishkin U.  1988.  The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time. Algorithmica. 3(1):329-346.

Apostolico A, Iliopoulos C, Landau GM, Schieber B, Vishkin U.  1988.  Parallel construction of a suffix tree with applications. Algorithmica. 3(1):347-365.

1987


Vishkin U.  1987.  Randomized parallel speedups for list ranking* 1. Journal of Parallel and Distributed Computing. 4(3):319-333.

Landau GM, Vishkin U, Nussinov R.  1987.  An efficient string matching algorithm with K substitutions for nucleotide and amino acid sequences*. Journal of theoretical biology. 126(4):483-490.

Azar Y, Vishkin U.  1987.  Tight comparison bounds on the complexity of parallel sorting. SIAM J. Comput.. 16(3):458-464.

Vishkin U.  1987.  An optimal parallel algorithm for selection. Parallel and Distributed Computing. 4:79-86.

1986


Maon Y, Schieber B, Vishkin U.  1986.  Parallel ear decomposition search (EDS) and st-numbering in graphs. Theoretical Computer Science. 47:277-298.

Landau GM, Vishkin U, Nussinov R.  1986.  An efficient string matching algorithm with k differences for nudeotide and amino acid sequences. Nucleic acids research. 14(1):31-31.

Landau GM, Vishkin U.  1986.  Efficient Parallel and Serial String Matching. Computer Science Department Technical Report. 221

Landau GM, Vishkin U.  1986.  Efficient string matching with k mismatches. Theoretical Computer Science. 43:239-249.

Landau GM, Vishkin U.  1986.  Introducing efficient parallelism into approximate string matching and a new serial algorithm. Proceedings of the eighteenth annual ACM symposium on Theory of computing. :220-230.

Cole R, Vishkin U.  1986.  Deterministic coin tossing with applications to optimal parallel list ranking. Information and Control. 70(1):32-53.

Cole R, Vishkin U.  1986.  Approximate and exact parallel scheduling with applications to list, tree and graph problems. 27th Annual Symposium on Foundations of Computer Science. :478-491.

Cole R, Vishkin U.  1986.  Approximate scheduling, exact scheduling, and applications to parallel algorithms. Proceedings Symposium on Foundations of Computer Science. :478-491.

Cole R, Vishkin U.  1986.  Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms. Proceedings of the eighteenth annual ACM symposium on Theory of computing. :206-219.

Cole R, Vishkin U.  1986.  The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time, Ultracomputer Note-108.

Alon N, Azar Y, Vishkin U.  1986.  Tight complexity bounds for parallel comparison sorting. 27th Annual Symposium on Foundations of Computer Science. :502-510.

1985


Tarjan RE, Vishkin U.  1985.  An efficient parallel biconnectivity algorithm. SIAM Journal on Computing. 14:862-862.

Perl Y, Vishkin U.  1985.  Efficient implementation of a shifting algorithm. Discrete applied mathematics. 12(1):71-80.

Landau GM, Vishkin U.  1985.  Efficient string matching in the presence of errors. Foundations of Computer Science, 1985., 26th Annual Symposium on. :126-136.

Coppersmith D, Vishkin U.  1985.  Solving NP-hard problems in [] almost trees': Vertex cover. Discrete applied mathematics. 10(1):27-45.

Bar-On I, Vishkin U.  1985.  Optimal parallel generation of a computation tree form. ACM Transactions on Programming Languages and Systems (TOPLAS). 7(2):348-357.

Vishkin U.  1985.  On efficient parallel strong orientation. Information Processing Letters. 20(5):235-240.

Vishkin U.  1985.  Optimal parallel pattern matching in strings. Information and Control. 67(1-3):91-113.

1984


Vishkin U.  1984.  A parallel-design distributed-implementation (PDDI) general-purpose computer. Theoretical Computer Science. 32(1-2):157-172.

Vishkin U.  1984.  An optimal parallel connectivity algorithm* 1. Discrete applied mathematics. 9(2):197-207.

Vishkin U.  1984.  Randomized speed-ups in parallel computation. Proceedings of the sixteenth annual ACM symposium on Theory of computing. :230-239.

Pages