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: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.
- 10/7.
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,
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:30-11:20 am, Thu 9:30-11:20 am. See you tomorrow in EAA 1100
at 9:30am!
- 09/03. The first class is on Tuesday, September 7, 16:30-17: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:30-11:20, Thu 9:30-11:20, in EAA 1100
-
Office Hours: Tue 11:30-12: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 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
macros
file) that you should use when preparing the scribe notes.