9 Randomness and Computation

Introduction

While it is safe to assume that any living adult is aware of the revolutionary impact of the computing technology on our society, we fear that few readers have a sense of the theory of computation. This contrast is not so surprising because people seem so overwhelmed by the wonders of this technology that they do not get to wonder about the theory underlying it. Consequently, the fascinating intellectual contents of the theory of computation is rarely understood by nonspecialists.

One goal of this essay is making a tiny contribution toward a possible change in this sour state of affairs, by discussing one aspect of the theory of computation: its connection to randomness. Our guess is that the suggestion that there is a connection between computation and randomness may meet the skepticism of some readers, because computation seems the ultimate manifestation of determinism.

To address this skepticism, we suggest considering what happens when a deterministic machine (or any deterministic process) is fed with a random input or just with an input that looks random. Indeed, one contribution of the theory of computation (further discussed in the section Pseudorandomness) is a definition of “objects that look random” (a notion that makes sense even if the real world is actually deterministic).

Still one may wonder whether we can obtain or generate objects that look random. For example, can we toss a coin (in the sense that one cannot feasibly predict the answer before seeing it)? Assuming a positive answer, we may also assume that unpredictable values can be obtained by other mechanical or electrical processes, which suggests that computers can also obtain such values. The question then is what benefit can be achieved by using such random (or unpredictable) values.

A major application of random (or unpredictable) values is to the area of cryptography (see the section Cryptography). In fact, the very notion of a secret refers to such a random (or unpredictable) value. Furthermore, various natural security concerns (e.g., private communication) can be met by employing procedures that make essential use of such secrets or random values.

Another major application of random (or unpredictable) values is to various sampling procedures. In the section Sublinear Time Algorithms, we consider a wider perspective on such procedures, viewing them as a special type of super-fast procedures called sublinear time algorithms. Such a procedure cannot afford to scan the entire input, but rather probes few (randomly) selected [Page 132]locations in it and, based on these few values, attempts to make a meaningful assertion regarding the entire input. Indeed, we assume that the reader is aware of the fact that random sampling allows approximation of the fraction of the population that votes for a particular candidate. Our point is that other global properties of the input, which are not merely averages of various types, can also be approximated by sampling.

Last, we mention that randomized verification procedures yield fascinating types of probabilistic proof systems, which are discussed in the section Probabilistic Proof Systems. In particular, such proof systems demonstrate the advantage of interaction (over one-directional communication) and the possibility of decoupling proving from learning (i.e., the possibility of proving an assertion without yielding anything beyond its validity). Other forms of probabilistic proof systems allow for superfast verification (based on probing few locations in a redundant proof, indeed as in the aforementioned sublinear-time algorithms).

...