# Uzi Vishkin

According to our database

^{1}, Uzi Vishkin## Awards

## ACM Fellow

ACM Fellow 1996, "One of the pioneers of parallel algorithms research, Dr. Vishkin's seminal contributions played a leading role in forming and shaping what thinking in parallel has come to mean in the fundamental theory of Computer Science.".

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### Homepages:

#### On csauthors.net:

## Bibliography

2016

FFT on XMT: Case Study of a Bandwidth-Intensive Regular Algorithm on a Highly-Parallel Many Core.

Proceedings of the 2016 IEEE International Parallel and Distributed Processing Symposium Workshops, 2016

POSTER: Easy PRAM-based High-Performance Parallel Programming with ICE.

Proceedings of the 2016 International Conference on Parallel Architectures and Compilation, 2016

2015

Oblivious Network RAM.

IACR Cryptology ePrint Archive, 2015

Oblivious Network RAM and Leveraging Parallelism to Achieve Obliviousness.

Proceedings of the Advances in Cryptology - ASIACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29, 2015

2014

Lazy Scheduling: A Runtime Adaptive Scheduler for Declarative Parallelism.

ACM Trans. Program. Lang. Syst., 2014

Parallel algorithms for Burrows-Wheeler compression and decompression.

Theor. Comput. Sci., 2014

Is multicore hardware for general-purpose parallel processing broken?

Commun. ACM, 2014

2013

Brief announcement: truly parallel burrows-wheeler compression and decompression.

Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures, 2013

2012

Brief announcement: speedups for parallel graph triconnectivity.

Proceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architectures, 2012

Better speedups using simpler parallel programming for graph connectivity and biconnectivity.

Proceedings of the 2012 PPOPP International Workshop on Programming Models and Applications for Multicores and Manycores, 2012

2011

A Low-Overhead Asynchronous Interconnection Network for GALS Chip Multiprocessors.

IEEE Trans. on CAD of Integrated Circuits and Systems, 2011

Resource-Aware Compiler Prefetching for Fine-Grained Many-Cores.

International Journal of Parallel Programming, 2011

Using simple abstraction to reinvent computing for parallelism.

Commun. ACM, 2011

Brief announcement: better speedups for parallel max-flow.

Proceedings of the SPAA 2011: Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2011

Panel Statement.

Proceedings of the 25th IEEE International Symposium on Parallel and Distributed Processing, 2011

Toolchain for Programming, Simulating and Studying the XMT Many-Core Architecture.

Proceedings of the 25th IEEE International Symposium on Parallel and Distributed Processing, 2011

Power-Performance Comparison of Single-Task Driven Many-Cores.

Proceedings of the 17th IEEE International Conference on Parallel and Distributed Systems, 2011

Improving Run-Time Scheduling for General-Purpose Parallel Code.

Proceedings of the 2011 International Conference on Parallel Architectures and Compilation Techniques, 2011

2010

Is teaching parallel algorithmic thinking to high school students possible?: one teacher's experience.

Proceedings of the 41st ACM technical symposium on Computer science education, 2010

Lazy binary-splitting: a run-time adaptive work-stealing scheduler.

Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 2010

A Low-Overhead Asynchronous Interconnection Network for GALS Chip Multiprocessors.

Proceedings of the NOCS 2010, 2010

Resource-Aware Compiler Prefetching for Many-Cores.

Proceedings of the Ninth International Symposium on Parallel and Distributed Computing, 2010

Thermal Management of a Many-Core Processor under Fine-Grained Parallelism.

Proceedings of the Euro-Par 2011: Parallel Processing Workshops - CCPI, CGWS, HeteroPar, HiBB, HPCVirt, HPPC, HPSS, MDGS, ProPer, Resilience, UCHPC, VHPC, Bordeaux, France, August 29, 2010

2009

Mesh-of-Trees and Alternative Interconnection Networks for Single-Chip Parallelism.

IEEE Trans. VLSI Syst., 2009

Brief announcement: performance potential of an easy-to-program PRAM-on-chip prototype versus state-of-the-art processor.

Proceedings of the SPAA 2009: Proceedings of the 21st Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2009

Algorithmic approach to designing an easy-to-program system: Can it lead to a HW-enhanced programmer's workflow add-on?

Proceedings of the 27th International Conference on Computer Design, 2009

HPPC 2009 Panel: Are Many-Core Computer Vendors on Track?

Proceedings of the Euro-Par 2009, 2009

2008

A pilot study to compare programming effort for two parallel programming models.

Journal of Systems and Software, 2008

XMT-GPU: A PRAM Architecture for Graphics Computation.

Proceedings of the 2008 International Conference on Parallel Processing, 2008

An area-efficient high-throughput hybrid interconnection network for single-chip parallel processing.

Proceedings of the 45th Design Automation Conference, 2008

Fpga-based prototype of a pram-on-chip processor.

Proceedings of the 5th Conference on Computing Frontiers, 2008

2007

Models for Advancing PRAM and Other Algorithms into Parallel Programs for a PRAM-On-Chip Platform.

Proceedings of the Handbook of Parallel Computing - Models, Algorithms and Applications., 2007

PRAM-on-chip: first commitment to silicon.

Proceedings of the SPAA 2007: Proceedings of the 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2007

Layout-Accurate Design and Implementation of a High-Throughput Interconnection Network for Single-Chip Parallel Processing.

Proceedings of the 15th Annual IEEE Symposium on High-Performance Interconnects, 2007

Toward Realizing a PRAM-on-a-Chip Vision.

Proceedings of the Euro-Par 2007 Workshops: Parallel Processing, 2007

2006

Bootstrapping Free-Space Optical Networks.

IEEE Journal on Selected Areas in Communications, 2006

Case study of gate-level logic simulation on an extremely fine-grained chip multiprocessor.

J. Embedded Computing, 2006

A bootstrapping model for directional wireless networks.

IEEE Communications Letters, 2006

A Mesh-of-Trees Interconnection Network for Single-Chip Parallel Processing.

Proceedings of the 2006 IEEE International Conference on Application-Specific Systems, 2006

2005

Bootstrapping Free-Space Optical Networks.

Proceedings of the 19th International Parallel and Distributed Processing Symposium (IPDPS 2005), 2005

2004

PRAM-On-Chip: A Quest for Not-So-Obvious Non-obviousness.

Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

Arbitrate-and-move primitives for high throughput on-chip interconnection networks.

Proceedings of the 2004 International Symposium on Circuits and Systems, 2004

2003

Towards a First Vertical Prototyping of an Extremely Fine-Grained Parallel Programming Approach.

Theory Comput. Syst., 2003

Deterministic Resource Discovery in Distributed Networks.

Theory Comput. Syst., 2003

2002

A Primal-Dual Parallel Approximation Technique Applied to Weighted Set and Vertex Cover

CoRR, 2002

Two techniques for reconciling algorithm parallelism with memory constraints.

SPAA, 2002

2001

Towards a first vertical prototyping of an extremely fine-grained parallel programming approach.

SPAA, 2001

Deterministic resource discovery in distributed networks.

SPAA, 2001

Evaluating the XMT Parallel Programming Model.

Proceedings of the 15th International Parallel & Distributed Processing Symposium (IPDPS-01), 2001

Evaluating the XMT Parallel Programming Model.

Proceedings of the High-Level Parallel Programming Models and Supportive Environments, 2001

What to Do with All this Hardware? (Invited Lecture).

Proceedings of the Combinatorial Pattern Matching, 12th Annual Symposium, 2001

2000

Experiments With List Ranking for Explicit Multi-Threaded (XMT) Instruction Parallelism.

ACM Journal of Experimental Algorithmics, 2000

A PRAM-on-Chip Vision (invited abstract).

Proceedings of the Seventh International Symposium on String Processing and Information Retrieval, 2000

A no-busy-wait balanced tree parallel algorithmic paradigm.

SPAA, 2000

Communication complexity of document exchange.

Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

1999

Trade-offs between Communication Throughput and Parallel Time.

J. Complexity, 1999

Experiments with List Ranking for Explicit Multi-Threaded (XMT) Instruction Parallelism.

Proceedings of the Algorithm Engineering, 1999

1998

Explicit Multi-Threading (XMT) Bridging Models for Instruction Parallelism (Extended Abstract).

SPAA, 1998

1997

From Algorithm Parallelism to Instruction-Level Parallelism: An Encode-Decode Chain Using Prefix-Sum.

SPAA, 1997

Conflict-Free Access to Multiple Single-Ported Register Files.

Proceedings of the 11th International Parallel Processing Symposium (IPPS '97), 1997

Approximate string searching.

Proceedings of the Pattern Matching Algorithms, 1997

1996

Sorting Strings and Constructing Digital Search Trees in Parallel.

Theor. Comput. Sci., 1996

A fast parallel algorithm for finding the convex hull of a sorted point set.

Int. J. Comput. Geometry Appl., 1996

Can Parallel Algorithms Enhance Seriel Implementation?

Commun. ACM, 1996

Efficient Approximate and Dynamic Matching of Patterns Using a Labeling Paradigm (extended abstract).

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995

Almost Fully-parallel Parentheses Matching.

Discrete Applied Mathematics, 1995

Parallel algorithms for database operations and a database operation for parallel algorithms.

Proceedings of IPPS '95, 1995

A note on reducing parallel model simulations to integer sorting.

Proceedings of IPPS '95, 1995

On a Technique for Parsing a String (Abstract).

CPM, 1995

1994

Top-Bottom Routing Around a Rectangle is as Easy as Computing Prefix Minima.

SIAM J. Comput., 1994

Finding Level-Ancestors in Trees.

J. Comput. Syst. Sci., 1994

A Primal-Dual Parallel Approximation Technique Applied to Weighted Set and Vertex Covers.

J. Algorithms, 1994

Biconnectivity Approximations and Graph Carvings.

J. ACM, 1994

On the Parallel Complexity of Digraph Reachability.

Inf. Process. Lett., 1994

On the Detection of Robust Curves.

CVGIP: Graphical Model and Image Processing, 1994

Pattern Matching in a Digitized Image.

Algorithmica, 1994

Symmetry breaking for suffix tree construction.

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Trade-offs between communication throughput and parallel time.

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 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. 23-25 January 1994, 1994

Optimal Parallel Approximation for Prefix Sums and Integer Sorting.

Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

Can Parallel Algorithms Enhance Serial Implementation?

Proceedings of the 8th International Symposium on Parallel Processing, 1994

Sorting Strings and Constructing Digital Search Trees in Parallel.

Proceedings of the 8th International Symposium on Parallel Processing, 1994

On a Parallel-Algorithms Method for String Matching Problems.

Proceedings of the Algorithms and Complexity, Second Italian Conference, 1994

1993

On Parallel Integer Merging

Inf. Comput., October, 1993

Recursive Star-Tree Parallel Data Structure.

SIAM J. Comput., 1993

Optimal Doubly Logarithmic Parallel Algorithms Based on Finding All Nearest Smaller Values.

J. Algorithms, 1993

Approximate Parallel Prefix Computation and its Applications.

Proceedings of the Seventh International Parallel Processing Symposium, 1993

A primal-dual parallel approximation technique applied to weighted set and vertex cover.

Proceedings of the 3rd Integer Programming and Combinatorial Optimization Conference, Erice, Italy, April 29, 1993

Two Dimensional Pattern Matching in a Digitized Image.

Proceedings of the Combinatorial Pattern Matching, 4th Annual Symposium, 1993

1992

A Parallel Blocking Flow Algorithm for Acyclic Networks.

J. Algorithms, 1992

Efficient Pattern Matching with Scaling.

J. Algorithms, 1992

Randomized Range-Maxima in Nearly-Constant Parallel Time.

Computational Complexity, 1992

Biconnectivity Approximations and Graph Carvings

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Pattern Matching in a Digitized Image.

Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

A Case for the PRAM As a Standard Programmer's Model.

Proceedings of the Parallel Architectures and Their Efficient Use, 1992

Methods in Parallel Algorithmics (Abstract).

Proceedings of the Mathematical Foundations of Computer Science 1992, 1992

Methods in Parallel Algorithmics and Who May Need to Know Them?

Proceedings of the Algorithms and Computation, Third International Symposium, 1992

Randomized Range-Maxima inNearly-Constant Parallel Time.

Proceedings of the Algorithms and Computation, Third International Symposium, 1992

1991

Approximate Parallel Scheduling. II. Applications to Logarithmic-Time Optimal Parallel Graph Algorithms

Inf. Comput., May, 1991

Deterministic Sampling - A New Technique for Fast Pattern Matching.

SIAM J. Comput., 1991

On Parallel Hashing and Integer Sorting.

J. Algorithms, 1991

Converting High Probability into Nearly-Constant Time-with Applications to Parallel Hashing (Extended Abstract)

Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Strutural Parallel Algorithmics.

Proceedings of the Automata, Languages and Programming, 18th International Colloquium, 1991

Towards a Theory of Nearly Constant Time Parallel Algorithms

Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

1990

Finding all nearest neighbors for convex polygons in parallel: A new lower bound technique and a matching algorithm.

Discrete Applied Mathematics, 1990

Deterministic Sampling-A New Technique for Fast Pattern Matching

Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Efficient Pattern Matching with Scaling.

Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 1990

On Parallel Hashing and Integer Sorting (Extended Summary).

Proceedings of the Automata, Languages and Programming, 17th International Colloquium, 1990

Some Triply-Logarithmic Parallel Algorithms (Extended Abstract)

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1989

Faster Optimal Parallel Prefix Sums and List Ranking

Inf. Comput., June, 1989

Fast Parallel and Serial Approximate String Matching.

J. Algorithms, 1989

Highly Parallelizable Problems (Extended Abstract)

Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

Recursive *-Tree Parallel Data-Structure (Extended Abstract)

Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

1988

On Finding a Minimum Dominating Set in a Tournament.

Theor. Comput. Sci., 1988

Matching Patterns in Strings Subject to Multi-Linear Transformations.

Theor. Comput. Sci., 1988

On Finding Lowest Common Ancestors: Simplification and Parallelization.

SIAM J. Comput., 1988

Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time.

SIAM J. Comput., 1988

Fast String Matching with k Differences.

J. Comput. Syst. Sci., 1988

Locating alignments with k differences for nucleotide and amino acid sequences.

Computer Applications in the Biosciences, 1988

The Accelerated Centroid Decomposition Technique for Optimal Parallel Tree Evaluation in Logarithmic Time.

Algorithmica, 1988

Parallel Construction of a Suffix Tree with Applications.

Algorithmica, 1988

On Finding Lowest Common Ancestors: Simplification and Parallelization.

Proceedings of the VLSI Algorithms and Architectures, 3rd Aegean Workshop on Computing, 1988

Efficient Parallel Triconnectivity in Logarithmic Time.

Proceedings of the VLSI Algorithms and Architectures, 3rd Aegean Workshop on Computing, 1988

Optimal Parallel Algorithms for Expression Tree Evaluation and List Ranking.

Proceedings of the VLSI Algorithms and Architectures, 3rd Aegean Workshop on Computing, 1988

1987

Tight Comparison Bounds on the Complexity of Parallel Sorting.

SIAM J. Comput., 1987

Randomized Parallel Speedups for List Ranking.

J. Parallel Distrib. Comput., 1987

Parallel Construction of a Suffix Tree (Extended Abstract).

Proceedings of the Automata, Languages and Programming, 14th International Colloquium, 1987

1986

Deterministic Coin Tossing with Applications to Optimal Parallel List Ranking

Information and Control, July, 1986

Parallel Ear Decomposition Search (EDS) and st-Numbering in Graphs.

Theor. Comput. Sci., 1986

Efficient String Matching with k Mismatches.

Theor. Comput. Sci., 1986

An efficient string matching algorithm with k differences for nucleotide and amino acid sequences.

Nucleic Acids Research, 1986

Introducing Efficient Parallelism into Approximate String Matching and a New Serial Algorithm

Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms

Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

Approximate and Exact Parallel Scheduling with Applications to List, Tree and Graph Problems

Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

Tight Complexity Bounds for Parallel Comparison Sorting

Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

Parallel Ear Decomposition Search (EDS) and St-Numbering in Graphs (Extended Abstract).

Proceedings of the VLSI Algorithms and Architectures, 1986

1985

Optimal Parallel Generation of a Computation Tree Form.

ACM Trans. Program. Lang. Syst., 1985

Trade-Offs Between Depth and Width in Parallel Computation.

SIAM J. Comput., 1985

An Efficient Parallel Biconnectivity Algorithm.

SIAM J. Comput., 1985

On Efficient Parallel Strong Orientation.

Inf. Process. Lett., 1985

Optimal Parallel Pattern Matching in Strings

Information and Control, 1985

Efficient implementation of a shifting algorithm.

Discrete Applied Mathematics, 1985

Solving NP-hard problems in 'almost trees': Vertex cover.

Discrete Applied Mathematics, 1985

Optimal Parallel Pattern Matching in Strings (Extended Summary).

Proceedings of the Automata, 1985

Efficient String Matching in the Presence of Errors

Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

1984

A Parallel-Design Distributed-Implementation (PDDI) General-Purpose Computer.

Theor. Comput. Sci., 1984

Simulation of Parallel Random Access Machines by Circuits.

SIAM J. Comput., 1984

Constant Depth Reducibility.

SIAM J. Comput., 1984

Finding Euler Tours in Parallel.

J. Comput. Syst. Sci., 1984

Solving NP-Hard Problems on Graphs That Are Almost Trees and an Application to Facility Location Problems.

J. ACM, 1984

An optimal parallel connectivity algorithm.

Discrete Applied Mathematics, 1984

Randomized and Deterministic Simulations of PRAMs by Parallel Machines with Restricted Granularity of Parallel Memories.

Acta Inf., 1984

Randomized Speed-Ups in Parallel Computation

Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

Finding Biconnected Components and Computing Tree Functions in Logarithmic Parallel Time (Extended Summary)

Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

1983

Dynamic Parallel Memories

Information and Control, March, 1983

An efficient distributed orientation algorithm.

IEEE Trans. Information Theory, 1983

Implementation of Simultaneous Memory Address Access in Models That Forbid It.

J. Algorithms, 1983

Parallel Computation on 2-3-Trees.

ITA, 1983

Parallel Dictionaries in 2-3 Trees.

Proceedings of the Automata, 1983

Trade-Offs between Depth and Width in Parallel Computation (Preliminary Version)

Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

1982

An O(n² log n) Parallel MAX-FLOW Algorithm.

J. Algorithms, 1982

An O(log n) Parallel Connectivity Algorithm.

J. Algorithms, 1982

Complexity of Finding k-Path-Free Dominating Sets in Graphs.

Inf. Process. Lett., 1982

Golden ratios in a pairs covering problem.

Discrete Mathematics, 1982

A Complexity Theory for Unbounded Fan-In Parallelism

Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982

1981

Finding the Maximum, Merging, and Sorting in a Parallel Computation Model.

J. Algorithms, 1981

Finding the maximum, merging and sorting in a parallel computation model.

Proceedings of the CONPAR 81: Conference on Analysing Problem Classes and Programming for Parallel Computing, 1981