Randomized Methods in Computation

Various Notes [2001 and 2011]

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.

This webpage provides access to lecture notes taken by students attending a course on Randomized Methods in Computation given in Spring 2001 and to material for a self-study compiled in Spring 2011.

Material available on-line

A webpage that provides access to lecture notes taken by students attending a course on the subject in Spring 2001.
In particular, this website provides access to preface to the lecture notes, a related text titled A Taste of Randomized Computations, brief summaries of all lectures, and notes to all 13 lectures in various formats (e.g., all material in one file [in gzip-ed PostScript (PS) format or in gzip-ed DVI format], and 13 individual lectures [in PSfiles]). Be warned of errors.
A webpage that provides access to material for a self-study compiled in Spring 2011.
This material is believed to superseded the foregoing lecture notes taken in 2001 by students (attending a course with a similar topic).

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