Randomized Methods in Computation
Notes for a Self-Study Course [Spring 2011]
Oded Goldreich
A variety of randomized methods are being employed
in the study of computation.
The aim of the suggested (self-study) 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 a new set of notes that
are suggested as a basis for the self-study course.
This material is believed to superseded the
lecture notes taken in 2001 by students attending a
course with a similar topic.
Material available on-line
- A
highly
tentative version, July 2011.
The material was compiled based on several older texts of mine.
In particular, much of it appears in my book
Computational Complexity: A Conceptual Perspective
(e.g., see Appendix D on
Probabilistic
Preliminaries and Advanced Topics in Randomization).
A list of topics (+ pointers to parts of the CC book) follows.
-
Basic probability and Laws of large numbers: Appendix D.1.
Two examples of an application of the probability method appear in
Appendix E (see Prop. E.1 and Footnote 14).
-
Pairwise independence and hashing: Section 8.5.1 and Appendix D.2.
-
Random walks on expanders: Section 8.5.3 and Appendix E.2.
-
Samplers and hitters: Appendix D.3
(or a more detailed survey).
-
Randomness Extractors: Appendix D.4.
-
Small bias spaces: Section 8.5.2
-
Approximate counting and uniform generation: Sections 6.2.2 and 6.2.4,
see also related Section 6.2.3 (optional).
-
Finally, see also the text
A Taste of Randomized Computations.
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 67--95, 2002.
Back to Oded Goldreich's homepage.
Copyright (C symbol) 2011 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.