A variety of randomized methods are being employed in the study of computation. The aim of the current course is to make the students familiar with some of these methods. We wish to stress three aspects regarding this course:

- This course focuses on
*methods*(i.e., tools and techniques) and not on concepts. - These methods are
*randomized*and so the result is often not ``(fully) explicit''. - The focus is on
*applications to the study of computation*.

- Elements of Probability Theory: Linearity of expectation, Markov Inequality, Chebyshev's Inequality, and Laws of Large Numbers (for pairwise-independent, $k$-wise independent, and fully independent samples).
- The
*Probabilistic Method*: Applications to Max3SAT and the existence of (3-regular) expander graphs. - Pairwise-independence, hashing, and related topics: Constructions (via matrices and low-degree polynomials), and applications (to Max3SAT, Approximate Counting, and Uniform Generation).
- Small bias spaces, the XOR Lemma, application to hardness of MaxQE(2).
- Expander graphs and random walks on them: Eigenvalues versus expansion, analysis of random walks (Hitter), and the Median-of-Average Sampler.
- Some randomized algorithms: Randomized Rounding (applied to Max3SAT), and Primality Testing (via SQRT extraction).

- Elements of Probability Theory
and the Probabilistic Method (2-3 lectures) :
- Linearity of expectation. Example: for every 3CNF there exists a truth assignment that satisfies 7/8 of the clauses.
- Markov Inequality and its underlying reasoning. Application: finding a truth assignment as above in probabilistic polynomial-time.
- Chebyshev's Inequality and its application to the sum/average of pairwise-independent random variables. Extension to $k$-wise independent sampling (with a proof).
- Chernoff/Hoeffding Bound (with a proof sketch).
- Using the Probabilistic Method to prove the existence of 3-regular expanders.
- Using the Probabilistic Method to prove the existence of (non-trivial) pseudorandom distributions.
- Lovasz Local Lemma.

- Pairwise-independence, hashing, and applications (2-3 lectures):
- Constructions: Using linear transformations (by arbitrary or Toeplitz matrices), and using low-degree polynomials (to obtain $k$-wise independence). Discussion of the technical difficulties regarding the finite field construction.
- Application to derandomizing the above Max3SAT algorithm.
- The (``Leftover'') Hashing Lemma.
- Approximate Counting and Uniform Generation of NP-witnesses with an NP-oracle.
- Hitters and Samplers (first encounter).

- Small bias spaces, codes, and applications (1-2 lectures):
- The distance from uniform distribution over $n$-bit strings versus the bias of the XOR of some of the bits.
- A construction of small bias sample spaces.
- Application: NP-hardness of MaxSAT for Quadratic Equations over GF(2).
- Relation to linear error correcting codes.

- Expander graphs and random walks on them (2-3 lectures):
- Eigenvalues versus expansion.
- Hitter: Analysis of a random walk on an expander.
- The Median-of-Averages Sampler.

- Randomness-Extractors (1-2 lectures): constructions and applications.
- Some randomized algorithms (2-3 lectures):
- Finding perfect matchings.
- Randomized Rounding (applied to MaxSAT).
- Primality Testing via Modular Square Root extraction.

- N. Alon and J.H. Spencer:
**The Probabilistic Method**, John Wiley & Sons, Inc., 1992. - O. Goldreich.
Modern Cryptography,
Probabilistic Proofs and Pseudorandomness.
Algorithms and Combinatorics series (Vol. 17), Springer, 1998.

Appendix B has been revised and appears as a separated text called A Taste of Randomized Computations. - O. Goldreich: Introduction to Complexity Theory - Lecture Notes, 1999 and 2002.
- R. Motwani and P. Raghavan:
**Randomized Algorithms**, Cambridge University Press, 1995.

In addition to the above general sources, we refer the reader to bibliographic notes presented at the end of each lecture.

Back to the lecture notes' main webpage or to Oded Goldreich's homepage.

Copyright (C symbol) 2001 by Oded Goldreich. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that new copies bear this notice and the full citation on the first page. Abstracting with credit is permitted.

This work may be published or be a basis for publication in the future. Copyright may be transferred without further notice and this version may no longer be accessible.