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