EECS 572: Randomness and Computation (Fall 2022)
Overview: Along with time and memory, randomness is a fundamental resource in computation. In many cases, randomness can be used to speed up computational tasks or reduce the memory footprint, creating an entire area of randomized algorithms. In applications such as cryptography, randomness is a necessary aspect of computation and such system crucially rely on access to high quality random bits (for example to produce a perfectly random secret key). Moreover for such applications, the information-theoretic view of randomness is used to mathematically model uncertainty. In machine learning and computational learning, randomness and statistics are essential tools to model the computational task. The use of randomness and particularly the probabilistic method constitutes an important proof technique in discrete mathematics. The range of applications of randomness in computation is simply too broad to break down on a short list. The aim of this course is to provide a mathematically rigorous exposition of the role of randomness in computation. The course will do so by showcasing examples from different application areas, such as those described above. Furthermore, the question of simulating randomness by deterministic computation as well as extraction of randomness from weak random sources will be discussed.
Instructor: Mahdi Cheraghchi
Tentative Syllabus:
Introduction
Suggested textbooks:
Prerequisites: Graduate standing or EECS 376 (formal prerequisites). The main requirement is mathematical maturity (and we will recall math bits as necessary). This course is, by its nature, quite mathsy, as mathematics is the fundamental pillar for understanding randomness. We will place some emphasis on mathematical rigor and discuss many important proofs in detail. You are expected to be comfortable with basic probability theory and linear algebra. As this is an elective course, a genuine interest in the subject is assumed. Advised prerequisites are: EECS 203, EECS 301, EECS 376, Math 217, or equivalents.
Evaluation criteria: Participation, Homework, Midterm Exam, Scribe Notes, Final Project.
Lectures: TuTh 10:30AM - 12:00PM 1017 DOW.
Discussions: Fr 2:30PM - 3:30PM 1017 DOW.
How to request permission to get ULCS or MDE credit for a graduate-level course:
Undergraduate students with interests in research, graduate studies, and/or deeper investigation into specific areas of CS can request permission to use credits from graduate-level EECS courses towards credit requirements for ULCS (for courses emphasizing individual work) or MDE/capstone (for courses emphasizing team projects).
To request permission to get ULCS or MDE credit for a graduate-level class, you should email the CPA for your program (csengadvisor@umich.edu for CoE students, cslsaadvisor@umich.edu for LSA students). In your email, you should identify yourself, the graduate-level course, which kind of credit you are requesting (ULCS or MDE), and how your request satisfies the following evaluation criteria:
Timing: You must submit a request prior to the first day of classes in the semester that you take the graduate-level course. Requests will not be granted retroactively.
Academic Standing: Your academic record at the time of your request should be strong - comparable to the record that a CSE graduate student could have had at a similar point in their undergraduate career.
Preparation: You should have done well in (and/or currently be doing well in) coursework that will prepare you to be successful in the graduate-level course. For example, for a graduate-level course covering advanced topics in area X, you should first take and do well in an undergraduate introductory course on X if one is offered, and if not, in CS core course(s) most closely related to area X.
Purpose: You should have a (brief) reason for why you want to take this course in particular. Typical examples of reasons are: that you are planning to apply to graduate school to study the field covered in the course; that you are working on undergraduate research in the area the course covers; that you took the introductory course in the topic and the professor of that course personally encouraged you to take this graduate-level course.
Complementarity: If you are pursuing another major or minor besides CS, the graduate-level course should make a distinctive contribution specifically to your CS degree. A graduate-level course that overlaps with coursework you have taken for another major/minor, or that also satisfies requirements for another major/minor, would in general not be approved. (Note: This does not mean you cannot take such a graduate-level class - it just means you would not be allowed to use it to satisfy ULCS/MDE credit requirements.)