Instructor: Grant Schoenebeck
GSI: Yuqing Kong
Time: Monday and Wednesday 3pm-4:30pm
Location: 1006 DOW
Randomness and the tools of probability theory have proven central in many areas of modern science, including, perhaps surprisingly, the design and analysis of algorithms. This course will be organized around the main tools and techniques (linearity of expectation, the second moment method, Chernoff bounds, martingales, Lovasz-Local Lemma, Monte Carlo Markov Chain, etc) used in probabilistic analysis of algorithms. Along the way, students will be exposed to a large variety of “classic” theoretical computer science works resulting from the applications of these same tools to both randomized algorithms and the analysis of random combinatorial objects (e.g. graphs, Boolean formulae) and deterministic algorithms applied to random inputs drawn from some distribution.
Advanced applications covered may include the Talagrand’s inequality; social networks; streaming algorithms; distributed algorithms; quantum computation; approximation algorithms; semidefinite programs; cryptographic protocols, and more. Specific advanced topics included will depend on the interests of the students.
After taking this course, students should be able to employ an array of tools for probabilistic analysis in their future research, as well understanding some of the classic applications of these techniques.
If you are interested in theoretical computer science (TCS) or tools of probabilistic analysis, it should be a fun course. It will assume basic theory understanding (at the level of 376) and basic probability theory, and the methodology will be that of formal mathematical proofs. The course will be targeted as an introductory course for CSE graduate students studying theory (very broadly speaking)—though others should benefit as well, including advanced undergraduates and graduate students from other areas.
This course will count for a theory breadth requirement CSE masters and PhD students and for a depth requirement for PhD students. However, if you do not have much interest in the course topics or TCS, there are easier ways to fulfill the theory requirement (e.g. EECS 586 requires less background / rigor).
To get an understanding if you have the required background, try reading through the lecture notes in the course text section below. This course will be aimed at a similar level. You do not need to understand everything (that is what the course is for), but if you are completely lost, you will likely have a difficult and not get much out of the course.
While there is no text book, we will largely follow the lecture notes of a previous course (tailoring and updating some material) EECS 271 by Alistair Sinclair at UC Berekeley.
The material covered will generally be classical computer science results with an emphasis on how probabilistic analysis is used in them.
This course will seek to actively engage students at many different levels. A key principal behind the design of this course is that “teaching is the best way to learn.” The students will be involved in the teaching processes.
There will usually be reading assignments that will be read before class and discussed or otherwise engaged with in class. These reading assignments will typically be accompanied by a “worksheet” that is designed by students and graded on effort.
The lectures will be taught in a variety of ways including: instructor lecturing, presentation roulette (where students need to present sections of material—with the help of the class!), discussion, and in-class problems.
In addition to lecture prep and worksheets, there will be several problem sets, a midterm exam, a relevant recent research presentation, the presentation of a topic, and a final exam. The final exam can be skipped by successfully completing a final project.
| worksheets / peer grading | 15% |
| problem sets / peer grading | 10% |
| midterm | 15% |
| teaching prep and in-class leadership | 14% |
| topic presentation | 13% |
and EITHER
| relevant recent research presentation | 13% |
| final exam | 20% |
OR
| Final Project | 33% |
This web-site is largely so that students thinking about the course can see more about it. Please see cTools for more up-to-date information on the course.