CMPT 881 - Pseudorandomness - Fall'04
Times & dates |
- 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:30-11: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.
Remember that next Tuesday, Oct 12, we'll have a two-hour lecture
(instead of our regular one-hour 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,
- 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).
Note the change of time and place of the class! We'll be meeting in East
Academic Annex (EAA 1100),
Tue 10:30-11:20 am, Thu 9:30-11:20 am. See you tomorrow in EAA 1100
- 09/03. The first class is on Tuesday, September 7, 16:30-17:20, in AQ 5020.
Course information handout: in
PostScript and in
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.
Valentine Kabanets (firstname.lastname@example.org), Office:
Lectures: Tue 10:30-11:20, Thu 9:30-11:20, in EAA 1100
Office Hours: Tue 11:30-12:30,
in ASB 9921 (or by appointment).
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 on-line from the author's home pages.) For the project,
you will need to write a short (at most
4-5 pages) report on the paper, and give
a 30-minute presentation in class.
For the scribes: Here is a
template tex file (and the
file) that you should use when preparing the scribe notes.