Randomized Algorithms

Motwani, R., & Raghavan, P. (1995). Randomized Algorithms. Cambridge University Press.

Type

Book

Intellectual base

Review or monograph

Year

1995

DOI

10.1017/cbo9780511814075

ISBN

9780521474658

DOI registrant

Cambridge University Press

Link

https://www.cambridge.org/9780521474658

Cited from

computer_science

Cited by

4 citations across 4 artifacts.

Each citation links to the sentence it supports in the citing article.

Primes

• Algorithm
  • The input-to-output deterministic-or-randomized mapping (Motwani & Raghavan, 1995)

    This sourceCanonical reference unifying deterministic and randomized algorithms as input-to-output mappings, distinguishing Las Vegas from Monte Carlo procedures.

• Livelock
  • Two further inferences follow. Randomness is a genuine solution, not a hack: in distributed systems and traffic alike, the cleanest break of a symmetric standoff is stochastic divergence, and much of the randomised-algorithm tradition is, at root, about livelock avoidance.

    This sourceRandomization (including backoff and symmetry-breaking) as a principled tool for breaking symmetric standoffs in distributed computation.

Domain-specific

• Isolation lemma
  • The entry states the combinatorial probability lemma and its reasoning role, not an implementation, cryptographic primitive, or guarantee that one trial will succeed.
• PSPACE
  • Input, work and output tape accounting, deterministic model and uniform polynomial bound must be fixed; time may be exponential and Savitch’s theorem gives equality with NPSPACE.

Verification

Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.

Does it back the claim? Not recorded. Neither this nor any other of the 4 citations of this work carries a recorded support check.

Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.

See how references were verified.

Links previously used in the corpus

Before the registry existed this work was also linked 1 other way.

• https://doi.org/10.1017/CBO9780511814075 ×1

Registry ID ref:c7e940fb6607 · see in the full table