Randomized algorithms

By Rajeev Motwani, P. Raghavan. 1995

For many applications, a randomized algorithm is either the simplest or the fastest algorithm available, and sometimes both. This book introduces the basic concepts in the design and analysis of randomized algorithms. The first part of the text presents basic tools such as probability theory and probabilistic analysis that are frequently used in algorithmic applications. Algorithmic examples are also given to illustrate the use of each tool in a concrete setting. In the second part of the book, each chapter focuses on an important area to which randomized algorithms can be applied, providing a comprehensive and representative selection of the algorithms that might be used in each of these areas. Although written primarily as a text for advanced undergraduates and graduate students, this book should also prove invaluable as a reference for professionals and researchers.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Slalom: Fast, Verifiable and Private Execution of Neural Networks in Trusted Hardware (2018, methodology): “Integrity for delegated matrix products follows from Freivald’s algorithm [39].”
Pinocchio: Nearly Practical Verifiable Computation (2013, neutral): “We use the multiplication of two matrices as our test application since it has appeared in several prior papers [25, 27], though simpler, non-cryptographic veriﬁcation procedures exist [51, § 7.1].”
Auditing black-box models for indirect influence (2016, neutral): “by standard Hoeffding tail bounds [18].”
Influence maximization: near-optimal time complexity meets practical efficiency (2014, unknown): “Our analysis frequently uses the Chernoff bounds [25]:”
Rank-Based Similarity Search: Reducing the Dimensional Dependence (2015, unknown): “The size of a random leveling, that is the sum of the cardinalities of its level sets, has expected value The expected height of a random leveling is logarithmic in j S j ; moreover, the probability of h greatly exceeding its expected value is vanishingly small (see [37]):”
The capacity of low-density parity-check codes under message-passing decoding (2001, unknown): “For proofs and applications of Azuma’s inequality see, for example, [16], [20].”
Set k-cover algorithms for energy efficient monitoring in wireless sensor networks (2003, unknown): “Combining equations, ∑ j α(Sj) ≥ OPT 2 .”
Randomized allocation processes (1997, unknown): “, [21, 23, 33]) can be used to show that with high probability at least one element from i∗ will be not chosen by any of the last n/2 ∗ balls.”
Gossip-based computation of aggregate information (2003, unknown): “Our algorithm is essentially a decentralized implementation of the simple randomized “Find” algorithm [25].”
Models and issues in data stream systems (2002, unknown): “Random samples can be used as a summary structure in many scenarios where a small sample is expected to capture the essential characteristics of the data set [65].”
A practical guide for using statistical tests to assess randomized algorithms in software engineering (2011, unknown): “To analyze the effectiveness of a randomized algorithm, it is important to study the probability distribution of its output or various performance metrics [44].”