The interplay between randomness and computation is one of the most fascinating scientific phenomena uncovered in the last couple of decades. This interplay is at the heart of modern cryptography and plays a fundamental role in complexity theory at large. Specifically, the interplay of randomness and computation is pivotal to several intriguing notions of probabilistic proof systems and is the focal of the computational approach to randomness. The four sets of lecture available below focus on these two subjects:

- Pseudorandomness - Part I (polynomial-time generators).
- Pseudorandomness - Part II (derandomization).
- Probabilistic Proof Systems - Part I (interactive and zero-knowledge proofs).
- Probabilistic Proof Systems - Part II (probabilistically checkable proofs).

Two of the lecture series focus on pseudorandomness and, specifically, pseudorandom generators. The first lecture series focuses on the case where the pseudorandom generator runs in polynomial-time and withstands any polynomial-time distinguisher. In particular, the distinguisher may be more complex (i.e., have a higher polynomial running time) than the generator. This framework is natural in the context of designing general-purpose pseudorandom generators that can be used in any efficient (i.e., polynomial-time) application. Furthermore, this framework is almost mandatory in cryptographic applications, where the adversary is typically willing to invest more effort than the legitimate users.

The second lecture series regarding pseudorandomness focuses on the case where the pseudorandom generator runs in exponential-time (w.r.t the seed length) and withstands distinguisher of running time bounded by a specific polynomial (in the length of the generator's output). In particular, the generator may be more complex than the distinguisher. This framework is natural in the context of de-randomization (i.e., converting randomized algorithms to deterministic ones). In this context, one may be willing to construct a special-purpose generator for each randomized algorithm (or each time bound), and scan through all possible seeds to the generator (thus not being intimidated by generators with exponential running-time).

For other notions of pseudorandom generators, the interested reader is referred to Chapter 3 of Modern Cryptography, Probabilistic Proofs and Pseudorandomness.

Loosely speaking, an *interactive proof system*
(see first lecture in the
third
lecture series)
is a game between a computationally bounded verifier
and a computationally unbounded prover whose goal is to convince
the verifier of the validity of some assertion.
Specifically, the verifier is probabilistic and its
time-complexity is polynomial in the length of the assertion.
It is required that if the assertion holds then the verifier
always accepts (when interacting with an appropriate prover strategy).
On the other hand, if the assertion is false then the
verifier must reject with probability at least $\frac12$,
no matter what strategy is being employed by the prover.
Thus, a ``proof'' in this context is not a fixed and static object,
but rather a randomized (dynamic) process
in which the verifier interacts with the prover.
*Zero-knowledge proofs*
(see second lecture in the
third
lecture series)
are interactive proofs
that yield nothing (to the verifier) beyond the fact that
the assertion is indeed valid.
That is, whatever the verifier can efficiently compute after interacting
with a zero-knowledge prover, can be efficiently computed
from the assertion itself (without interacting with anyone).
Thus, zero-knowledge proofs exhibit an extreme contrast
between being convinced of the validity of a statement
and learning anything in addition
(while receiving such a convincing proof).

In contrast to the above,
*probabilistically checkable proofs (PCPs)*
(see
last
lecture series)
may be though as an augmentation of written proofs
allowing very fast probabilistic verification via direct access
to randomly selected portions of the (redundant) proof.
Typically, the verifier access only a tiny part of the proof,
and this part is much smaller than an ordinary proof.
Again, it is required that if the assertion holds
then the verifier always accepts (when given access to an
adequate proof); whereas, if the assertion is false
then the verifier must reject with probability at least $\frac12$,
no matter which false proof is presented to it.

Other types of probabilistic proof systems are discussed in Chapter 2 of Modern Cryptography, Probabilistic Proofs and Pseudorandomness.

We refer the reader to Lecture Notes on Complexity Theory.

Back to the top or to Oded Goldreich's homepage.