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:
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.