an essay by Oded Goldreich

Auxiliary title: Randomness and Complexity

The interplay of randomness and computation is at the heart of modern cryptography and plays a fundamental role in the design of algorithms and in the study of computation at large. Specifically, this interplay is pivotal to several intriguing notions of probabilistic proof systems (e.g., interactive proofs, zero-knowledge proofs, and probabilistically checkable proofs), is the focal of the computational approach to randomness, and is essential for various types of sub-linear time algorithms. This essay provides a brief outline of these connections, and is intended mainly for non-TOC readers.

Versions available on-line

A preliminary version [Dec. 2005], and revisions [Feb. 2006].
Last PDF version (Feb. 2006).

A kind of introduction (extract)

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. Furthermore, people tend to think of computing in the concrete terms in which they have lastly encountered it rather than in general terms. Consequently, the fascinating intellectual contents of the theory of computation is rarely understood by non-specialists.

One goal of this essay is making a tiny contribution towards 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 is a definition of ``objects that look random'' (a notion which 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 and/or electrical processes, which suggest 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. 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 and/or random values.

Another major application of random (or unpredictable) values is to various sampling procedures. At the end of this essay, we consider a wider perspective on such procedures, viewing them as a special type of super fast procedures called sub-linear time algorithms. Such a procedure cannot afford to scan the entire input, but rather probes few (randomly) selected 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 to approximate 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.

Lastly, we mention that randomized verification procedures yield fascinating types of 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 super fast verification (based on probing few locations in a redundant proof, indeed as in the aforementioned sublinear-time algorithms).

Before discussing the foregoing applications of randomness in greater length, we provide a somewhat wider perspective on the theory of computation as well as present some of its central conventions. We will also clarify what randomness means in that theory (and in this article).

Back to homepage.