Live briefing
Everything about Randomized algorithm
Algorithm that employs a degree of randomness as part of its logic or procedure
A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random determined by the random bits; thus either the running time, or the output are random variables. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: Randomized algorithmA 5-minute orientation
- Skim a recent paper: Random Forest Algorithm OverviewInfluential work since 2022
- Pick up a classic book: Study of one- and two-dimensional filtering and deconvolution algorithms for a streaming array computerThe most-reprinted book on the subject
- Read the landmark paper: Segmentation of brain MR images through a hidden Markov random field model and the expectation-maximization algorithmCited 6,669 times
- Go sideways: BPP (complexity)A closely related topic
- Go sideways: RL (complexity)A closely related topic
📖 Definitions
Noun Any algorithm that uses randomness as part of its logic.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
Segmentation of brain MR images through a hidden Markov random field model and the expectation-maximization algorithm
A Randomized Kaczmarz Algorithm with Exponential Convergence
A Randomized Algorithm for Principal Component Analysis
An Efficient Randomized Algorithm for Detecting Circles
A strongly competitive randomized paging algorithm
A Randomized Algorithm for Closest-Point Queries
Randomized Quantum Algorithm for Statistical Phase Estimation
An accelerated randomized Kaczmarz algorithm
🆕 Influential since 2022
Random Forest Algorithm Overview
Distributed Randomized Gradient-Free Mirror Descent Algorithm for Constrained Optimization
Communication-Efficient Randomized Algorithm for Multi-Kernel Online Federated Learning
Algorithm 1043: Faster Randomized SVD with Dynamic Shifts
Randomized Average Kaczmarz Algorithm for Tensor Linear Systems
📚 Books worth reading
- 📕Study of one- and two-dimensional filtering and deconvolution algorithms for a streaming array computerGeorge E. Ioup · 1985
Non-uniform random variate generationLuc Devroye · 1986
Automatic nonuniform random variate generationWolfgang Hörmann · 2004
The Discrepancy MethodBernard Chazelle · 2000
Concentration of measure for the analysis of randomized algorithmsDevdatt Dubhashi · 2009- 📕Development of algorithms and error analyses for the short baseline lightning detection and ranging systemStan Starr · 1998
Random generation of treesLaurent Alonso, René Schott · 1994- 📕Algorithms for random graphs with bounded degreeKrystyna Teresa Balińska · 1996
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- BPP (complexity) In computational complexity theory, a branch of computer science, bounded-error probabilistic polynomial time (BPP) is the class of decision problems solvable…
- RL (complexity) Randomized Logarithmic-space (RL), sometimes called RLP (Randomized Logarithmic-space Polynomial-time), is the complexity class of computational complexity…
- Monte Carlo algorithm In computing, a Monte Carlo algorithm is a randomized algorithm whose output may be incorrect with a certain (typically small) probability. Two examples…
- Yao's principle In computational complexity theory, Yao's principle (also called Yao's minimax principle or Yao's lemma) relates the performance of randomized algorithms…
- L (complexity) In computational complexity theory, L (also known as LSPACE, LOGSPACE or DLOGSPACE) is the complexity class containing decision problems that can be solved…
- Nondeterministic algorithm In computer science and computer programming, a nondeterministic algorithm is an algorithm that, even for the same input, can exhibit different behaviors…
- Time complexity In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm…
- Complexity class In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". The two most commonly…