CMPT 881  Pseudorandomness  Fall'04
Instructor 
Times & dates 
Project 
Homeworks 
Lectures 
Relevant links
 11/17. Next Tuesday, Nov 23, the class will meet in ASB 9705
(instead of our usual room in EAA). The time remains the same: 10:3011:20am.
 11/2. Homework 2 is now posted (see below).
 10/18. There are no classes this week, and no class on Tuesday
of the next week. The course will resume on Thu, Oct 28.
 10/7.
Remember that next Tuesday, Oct 12, we'll have a twohour lecture
(instead of our regular onehour lecture). We start at 10:30 (as usual),
and continue till 12:20. See you there!
 10/3. The first homework assignment is now available (see below,
under "Homeworks").
 10/2. The list of possible papers for your course project are
now posted (see below, under "Project").
 09/16. Please attend Madhu Sudan's lecture tomorrow, Sept 17,
at 1:30 pm, AQ 3153 (followed by a reception at 3pm in EAA 1100).
 09/8.
Note the change of time and place of the class! We'll be meeting in East
Academic Annex (EAA 1100),
Tue 10:3011:20 am, Thu 9:3011:20 am. See you tomorrow in EAA 1100
at 9:30am!
 09/03. The first class is on Tuesday, September 7, 16:3017:20, in AQ 5020.

Past Announcements
Course information handout: in
PostScript and in
PDF
Course Text: There is no textbook for this
course. Below are a few suggested sources for some of the material
to be covered.
 lecture notes on some basics
of algebra by Madhu Sudan (MIT)
 lecture notes for a similar
course on pseudorandomness taught by Salil Vadhan (Harvard)
 lecture notes
for a course on expander graphs taught by Nati Linial and Avi Wigderson (Hebrew University).
 Derandomizing complexity classes
an extensive survey on derandomization by Peter Bro Miltersen.
 the book "Randomized Algorithms" by R. Motwani and P. Raghavan is an excellent source on various techniques
for constructing randomized algorithms.
 the book "Modern Cryptography, Probabilistic Proofs and Pseudorandomness" by Oded Goldreich has a
survey chapter on pseudorandom generators, which provides an excellent introduction to the area.
Instructor:
Valentine Kabanets (kabanets@cs.sfu.ca), Office:
ASB 9921

Lectures: Tue 10:3011:20, Thu 9:3011:20, in EAA 1100

Office Hours: Tue 11:3012:30,
in ASB 9921 (or by appointment).
Important dates

Assignments due: Assignment 2 is due November 25.
Here is a
list of possible papers that you can choose for
your course project. There are many more papers relevant to the topic
of the course. If you want to read a paper not on the list, please talk
to me to get an approval of your chosen paper. (Most of the papers on the
list are available online from the author's home pages.) For the project,
you will need to write a short (at most
45 pages) report on the paper, and give
a 30minute presentation in class.
For the scribes: Here is a
template tex file (and the
macros
file) that you should use when preparing the scribe notes.