Pseudorandomness is the study of e�iciently 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.
Lecture: MW15:30-16:45, Siebel 1214.
Staff:
role | name | (netid) | office hour |
---|---|---|---|
instructor: | Prof. Michael A. Forbes | (miforbes) | M17 (or by appointment), Siebel 3220 |
The calendar lists lecture topics, associated lecture materials, and auxiliary reading. It also lists the problem sets with release- and due-dates.
The forum for the class is Piazza (code).
The submission server for the class is Gradescope (code). When submitting assignments, student must use their @illinois.edu netid so the course staff can appropriately map students to submissions.
A students grade in the course compromises of:
The lectures for the course will be in-person, except on occasions when announced otherwise.
Lectures will not be recorded but recordings from previous versions of this course will be made available on the calendar. As this recordings are from the past, there may be some differences with the in-person lecture.
The main materials for the class are the above-mentioned lecture materials. Auxiliary pointers to written material will be listed for each lecture, and are approved materials for collaboration purposes.
The following are approved materials.
Familiarity with discrete mathematics (cs173), models of computation (cs374, cs475), algorithms (cs473), linear algebra , and polynomials ; as well as mathematical maturity.
The course will use Piazza as a forum.
The forum will be the sole source of announcements from the course staff. Students should sign-up promptly to avoid missing such announcements.
The forum is also intended for students to connect amongst themselves on all course-related issues, except when such discussion reveals significant information about solutions to pending assignments. Posts can be made anonymously to other students (but not to the course staff). The students in the course can sometimes offer the best help; please make this resource the best it can be.
The forum is finally meant for private communication between the students and the course staff, especially for logistical matters such as scheduling conflicts. Emailing course staff directly is heavily discouraged. While the forum can be used for private help from the course staff on course content, a quicker and more thorough response is often achieved through a public discussion.
In order to avoid distracting other students, any student (without prior accommodation) who uses a computing device with a screen that does not lie flat on table/lap must sit in the back half of the lecture hall. Some examples:
If you require an accommodation with regards to this policy, please contact the course staff.
Coursework must be submitted individually. However, verbal discussion (oral or electronic) with other students in the course is highly encouraged, subject to the constraint that submitted psets must list all such collaborators. However, the composition of the pset submissions must be solely the work of the listed author. In particular, no sharing of written solutions is allowed.
Students are allowed to use any approved course materials, or discussions with students or staff affiliated with the course. Students are forbidden from using any other resources; this includes websites and textbooks, as well as human and artificial intelligence.
The first violation of academic integrity is a zero for the entire assignment. The second violation is a reduction of 1 letter grade.
A students grade in the course compromises the 6 psets of 4 problems each. All problems from problem sets are worth the same number of points.
Regrade requests will be open for two weeks after an assignment is returned. Regrade requests will result in the entire assignment in being regraded; as a result the overall score may decrease.
Sample solutions will be distributed to students when the problem sets are returned (please keep the internet free of easily-found solutions!). These sample solutions will be selected from student submissions (with names omitted). Please inform the course staff if you wish to opt-out of ever being selected.
Students are highly encouraged to turn-in assignments on-time to avoid falling behind on the material, and to incentivize this any late problem sets will automatically lose 10% in value. However, to be flexible, for each pset students can automatically take (without asking) a 3-day extension (72 hours). The extension (and resulting penalty) applies to the entire problem set, regardless of whether a partial submission was made on time. Problem sets will not be accepted past this 3-day extension window.
Note that based on historical grade data, if a student submitted all problem sets late then the 10% penalty would likely result in a drop of 1 letter grade.
Figures are highly encouraged. Many algorithms act on combinatorial objects such as graphs, and discussing such objects without a figure is a pain to write, and to read.
To use your time wisely, students are encouraged to focus on content of their coursework over format. However, content and format are not fully independent. As such, students are suggested to consider the following advice on submission formats.