Randomized Methods in Computation
(Preface to Lecture Notes)
Oded Goldreich
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.
Specific topics included:
- 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).
The lecture notes were taken by students attending the course
Randomized Methods in Computation,
which was given by Oded Goldreich in the Spring 2001 semester
at the Weizmann Institute of Science.
The background and level of the students attending the class was
quite mixed, and this forced a slower pace than originally planned.
The Original Plan
- 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.
State and usage of these notes
These notes are neither complete nor fully proofread,
let alone being far from uniformly well-written
(although the notes of some lectures are quite good).
Furthermore, due to the mixed level of the class,
the pace was slower than originally planned,
and so these notes include less material than originally intended.
Still, we do believe that these notes suggest a good outline
for a course on the subject.
Bibliographic Notes
There are several books and lecture notes
that cover parts of the material. These include:
However, the presentation of the material in the current
lecture notes does not necessarily follow these sources.
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.