The Random Adversary: A Lower-Bound Technique for Randomized Parallel Algorithms

DOI10.1137/S0097539791224030zbMATH Open0885.68061OpenAlexW2008874980MaRDI QIDQ4376188

Philip MacKenzie

Publication date: 10 February 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539791224030

zbMATH Keywords

parallel computationparallel algorithmslower boundsload balancingrandomized parallel algorithmsPRAM modelexpected time

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed algorithms (68W15)

Related Items (1)

A reduction theorem for randomized distributed algorithms under weak adversaries

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Parallel randomized load balancing: a lower bound for a more general model 👍 👎
• From randomizing polynomials to parallel algorithms 👍 👎
• Parallel Randomized Load Balancing: A Lower Bound for a More General Model 👍 👎
• Lower time bounds for randomized computation 👍 👎
• Robust parallel computations through randomization 👍 👎

This page was built for publication: The Random Adversary: A Lower-Bound Technique for Randomized Parallel Algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4376188)