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:

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.