Proceedings of the Third Workshop on
Randomized Parallel Computing

IPDPS 1998 Workshop

Foreword:

There are a total of 15 papers in this volume. Twelve of these papers were written by authors upon invitation. The other three papers were selected from among the papers submitted, in response to the call for papers, to the Third Workshop on Randomized Parallel Computing. The workshop was held on April 3, 1998 in Orlando, FL and was sponsored by the IEEE Computer Society Technical Committee on Parallel Processing. Since some of the papers in this volume represent reports of continuing research, it is anticipated that more polished versions will appear in scientific journals. The program committee thanks all the authors who accepted our invitation to write papers and those who submitted papers to the workshop.

Sanguthevar Rajasekaran, Chair
Panos Pardalos, Co-Chair

Program Committee:

Pankaj K. Agarwal, Duke U
Susanne Albers, Max-Planck Institute
Sandeep N. Bhatt, Bellcore
Frank Hsu, Fordham U
Oscar Ibarra, U of California, SB
Tom Leighton, MIT
Bruce Maggs, CMU
Michael A. Palis, Rutgers U
Panos Pardalos, U of Florida
Greg Plaxton, U of Texas
Sanguthevar Rajasekaran, U of Florida
Abhiram Ranade, IIT Bombay
Sartaj Sahni, U of Florida
Paul Spirakis, U of Patras


Program:

A Survey of Randomness and Parallelism in Comparison Problems
Danny Krizanc

Capturing the Connectivity of High-Dimensional Geometric Spaces by Parallelizable Random Sampling Techniques
David Hsu, Lydia E. Kavraki, Jean-Claude Latombe, Rajeev Motwani

Optimal Bounds on Tail Probabilities - A Simplified Approach
Aviad Cohen, Yuri Rabinovich, Assaf Schuster, Hadas Shachnai

Random Sampling Techniques in Parallel Computation
Rajeev Raman

Randomization in Parallel Stringology
S. Muthukrishnan

Randomized Parallel Prefetching and Buffer Management
Peter J. Varman

Parallel Algorithms for Finite Automata Problems
B. Ravikumar

Randomized Routing and PRAM Emulation on Parallel Machines
David S.L. Wei

On Randomized and Deterministic Schemes for Routing and Sorting on Fixed-Connection Networks
Torsten Suel

High Performance Linear Algebra Package LAPACK90
Jack Dongarra, Jerzy Wassniewski

Ultrafast Randomized Parallel Construction and Approximation Algorithms for Spanning Forests in Dense Graphs
Anders Dessmark, Carsten Dorgerloh, Andrzej Lingas, Jurgen Wirtgen

Parallel Randomized Techniques for Some Fundamental Geometric Problems: A Survey
Suneeta Ramaswami

Randomized Algorithms on the Mesh
Lata Narayanan

Implementing Parallelism in Random Discrete Event-Driven Simulation
Marc Bumble, Lee Coraor

Reconfigurable Wormhole Networks: A Realistic Approach
Jose L. Sanchez, Jose M. Garcia, Francisco J. Alfaro