Category:Randomized algorithms

• Randomized algorithm

A

• Algorithmic information theory
• Approximate counting algorithm
• Arthur–Merlin protocol
• Atlantic City algorithm
• Average performance
• Average-case complexity
• Averaging argument

B

• Basin-hopping
• Baum–Welch algorithm
• Biology Monte Carlo method

D

• Derandomization

E

• Entropy compression
• Expected linear time MST algorithm

F

• First-order second-moment method
• Fisher–Yates shuffle
• Freivalds' algorithm

K

• Karloff–Zwick algorithm

L

• Las Vegas algorithm
• Linear partial information
• List update problem

M

• Mean-field particle methods
• Monte Carlo algorithm
• Monte Carlo method
• Morris method
• Multilevel Monte Carlo method
• Multiplicative weight update method

N

• Nested sampling algorithm

P

• Principle of deferred decision
• Probabilistic complexity theory
• Probabilistic Turing machine
• Probabilistically checkable proof
• Property testing

Q

• PCP theorem

R

• Random permutation
• Random priority item allocation
• Random self-reducibility
• Reservoir sampling

S

• Set balancing
• Simultaneous perturbation stochastic approximation
• Sipser–Lautemann theorem
• Solovay–Strassen primality test

W

• With high probability

Y

• Yao's principle