A Taste of Randomized Computations
Oded Goldreich
The purpose of
this
text is to demonstrate the usage of
randomization in a variety of computational settings.
Our choice is governed by the desire to focus on the randomization
aspect of the solution and avoid any complicated details that
are due to other aspects of the computational problem.
Thus, we avoid any example that requires
substantial problem-specific background.
Our 13 examples are grouped in three (subjective) categories:
- Randomized Algorithms (for traditional algorithmic problems)
- Approximate Counting of DNF satisfying assignments
- Finding a perfect matching
- Testing whether polynomials are identical
- Randomized Rounding applied to MaxSAT
- Primality Testing
- Testing Graph Connectivity via a random walk
- Finding minimum cuts in graphs
- Randomized Reductions (or Randomness in Complexity Theory)
- Reducing (Approximate) Counting to Deciding
- Two-sided error versus one-sided error
- The permanent: Worst-Case versus Average Case
- Randomness in Distributed Computing
- Testing String Equality
- Routing in networks
- Byzantine Agreement
We stress that our presentation is merely aimed at demonstrating
the usage of randomization, and that no attempt was made to present
a coherent theory of randomized computation.
Furthermore, our presentation tends to be laconic
(i.e., it lacks some technical details as well as wider perspective).
Back to Oded Goldreich's homepage.