ANNOUNCEMENTS
ABOUT
Class: MW2-3:15, Siebel 1302
Instructor: Prof. Michael A. Forbes
Office Hours: M3:15, W1:00, by appointment, at Siebel 3220
Schedule: see here for schedule of lecture topics & outlines, pset release/due dates, and relevant textbook sections.
DESCRIPTION
Pseudorandomness is the study of efficiently constructing objects that share desirable features of random objects, yet require no randomness to describe. The theory of pseudorandomness influences and draws from areas in computer science such as computational complexity, algorithms, and cryptography; as well as areas of mathematics such as combinatorics and number theory. This course will explore the core aspects of pseudorandomness by constructing foundational pseudorandom objects such as expander graphs, error-correcting codes, randomness extractors and pseudorandom generators, as well as presenting key techniques such as spectral graph theory, (derandomized) concentration bounds, and the polynomial method.
Prerequisites: basic familiarity with probability, linear algebra, algorithms, and computational complexity
REFERENCES
This class is a duplicate of one given at Harvard. As such, we will cover the book Pseudorandomness (pdf) by Vadhan. This can be downloaded from the publishers website when on-campus.
The instructor will also provide lecture outlines (see the schedule), in a preliminary .txt file as well as more flushed-out handwritten notes.
GRADING
PROBLEM SETS:
There will be 6-7 biweekly homeworks, where each problem is worth 10 points.
Submission Policy: Homeworks will be posted by 2pm on the day of release, and are due 2pm on the due date. Hard copies can be submitted in-person at the beginning of class. Alternatively, electronic (pdf) copies can be submitted by email to the instructor, where the subject line should start with [cs598] and the filename must be of the form psN-NETID.pdf (N = pset number, NETID = your netid).
Collaboration Policy: Students are highly encouraged to collaborate in small groups. However, this must be a two-way collaboration. Students should not dictate complete solutions to other students, either verbally or written. Solutions must be written independently regardless of collaboration, and psets must list the collaborators you worked with.
Late Policy: Students are highly encouraged to turn-in assignments on-time to avoid falling behind on the material. However, to be flexible, students have a total of 6 late days (24 hours each) which can be applied without penalty. Late days will be rounded up to integral values for each pset. Late psets must be submitted electronically.
TYPOS:
All textbooks have typos, and the one used in this class is no different (at least 4 typos in the first 20 pages). Students are encouraged to hunt for typos, including simple grammatical or typesetting issues. A list of found typos (by this semester's students) is listed in the errata page. The first student to find a given typo will be awarded 1-5 bonus points based on the magnitude of the typo. Typos can be submitted via email to the instructor.