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:

Specific topics included: 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

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.