Accession Number:

ADA109047

Title:

On the Power of Probabilistic Choice in Synchronous Parallel Computations

Descriptive Note:

Technical rept.

Corporate Author:

HARVARD UNIV CAMBRIDGE MA AIKEN COMPUTATION LAB

Personal Author(s):

Report Date:

1981-11-01

Pagination or Media Count:

31.0

Abstract:

This paper introduces probabilistic choice to synchronous parallel machine models in particular parallel RAMs. The power of probabilistic choice in parallel computations is illustrated by Olog n time algorithms for connectivity and recognizing bipartite graphs and Olog n squared time algorithms for testing if a graph has a perfect matching, testing in time On irreducibility of polynomials over finite fields. We characterize the computational complexity of time, space, and processor bounded probabilistic sequential RAMs. We show that parallelism uniformly speeds up time bounded probabilistic, sequential RAM computations by nearly a quadratic factor. We also show that probabilistic choice can be eliminated from parallel computations by introducing nonuniformity. Author

Subject Categories:

  • Statistics and Probability
  • Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE