Randomized Methods in Computation
Lecture Notes [Spring 2001]
Oded Goldreich
The material avialable from
this page is mostly superseded by new material available from
a new webpage (dating to 2011).
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.
This webpage provides access to lecture notes on
Randomized Methods in Computation,
a course given by Oded Goldreich in Spring 2001 at the Weizmann Institute.
Material available online
 Preface to the lecture notes.
 Summaries
(+ links to all 13 individual lecture notes).
 All 13 lecture notes (plus bibliographic notes) in one file:
 The 13 individual lectures (in PSfiles):
 Lecture
1: Probability and the Probabilistic Method.
 Lecture
2: Laws of Large Numbers and Existence of Expanders.
 Lecture
3: Small PairwiseIndependent Sample Spaces.
 Lecture
4: Small PairwiseIndependent Sample Spaces (cont.) and Hash Functions.
 Lecture
5: Approximate Counting and Uniform Generation (Part 1).
 Lecture
6: Approximate Counting and Uniform Generation (Part 2).
 Lecture
7: Small Bias Sample Spaces (Part 1).
 Lecture
8: Small Bias Sample Spaces (Part 2).
 Lecture
9: Expanders and Eigenvalues.
 Lecture
10: Random Walks on Expanders.
 Lecture
11: Primality Testing (via SQRT extraction).
 Lecture
12: Hitters and Samplers.
 Lecture
13: Randomized Rounding.
 Errata:
In general, the notes contain several errors.
Some of these errors are noted HERE
Additional entries are welcome...
Additional recommended reading

N. Alon and J.H. Spencer: The Probabilistic Method.
John Wiley Sons, Inc., 1992.

O. Goldreich,
Computational Complexity: A Conceptual Perspective,
Cambridge University Press, 2008.

R. Motwani and P. Raghavan: Randomized Algorithms.
Cambridge University Press, 1995.

R. Shaltiel: Recent Developments in Explicit Constructions of Extractors.
In Current Trends in Theoretical Computer Science:
The Challenge of the New Century,
Vol 1: Algorithms and Complexity, World scietific, 2004.
(Editors: G. Paun, G. Rozenberg and A. Salomaa.)
Preliminary version in Bulletin of the EATCS 77, pages 6795, 2002.
Back 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.