CSE 525: Randomized Algorithms and Probabilistic Analysis (Winter 2021)
[course description
| lectures
| assignments
| discussion board
| zoom links
| related material]
| important announcements]
important announcements
lectures
See references and key below
- Lecture 1 (Jan 4) Overview, Matrix-product verification [MU 1.3], [MR 7.1], fingerprinting ([MR] Section 7.4,
[CG] Section 2.2.1), MAX-CUT ([MU] Section 6.2.1); Method of conditional expectation [V Sections 3.4-3.5]
- Lecture 2 (Jan 6):
Randomized Minimum Spanning Tree
- Lecture 3 (Jan 11): Markov and Chebychev Inequalities [MU 3.1-3.3],
Chernoff-Hoeffding bounds [MU, Chapter 4, MR 4.1], [DP, Chapter 1], [WS, 5.10]
- Lecture 4 (Jan 13): Balls in Bins [MU, 5.2-5.4]
- No class (Martin Luther King, Jr. Day) (Jan 18)
- Lecture 5 (Jan 20): Reachable size estimation, Intro randomized rounding
- Lecture 6 (Jan 25): Randomized rounding of LPs [WS, Sections 1.2, 1.7, 5.4, 5.11]
- Lecture 7 (Jan 27): Randomized rounding of SDPs [WS, Sections 6.1-6.2, 6.5]
- Lecture 8 (Feb 1): Finish randomized rounding of SDPs; Start online bipartite matching
- Lecture 9 (Feb 3): Online bipartite matching
- Lecture 10 (Feb 8): 2nd moment method and random graphs [MU 6.1, 6.5-6.6][AS Chap 4,10.7]
- Lecture 11 (Feb 10): Lovasz Local Lemma [MU 6.7-6.9]
- No class (President's Day) (Feb 15)
- Lecture 12 (Feb 17): Markov chains and random walk based bipartite matching [MU Chapter 7, MR Sections 6.1-6.3, 6.6]
- Lecture 13 (Feb 22): Random walks on graphs [MU Chapter 7, MR Sections 6.1-6.3, 6.5-6.7]
- Lecture 14 (Feb 24): Monte Carlo methods and approximate counting [MU Chapter 11,
this survey and references
therein].
- Lecture 15 (Mar 1): Coupling [MU Chapter 12][LPW Chapter 5]
- Lecture 16 (Mar 3) Martingales [MU, Chapter 13][LPW Chapter 17]
- Lecture 17 (Mar 8) More on martingales, start online learning
- Lecture 18 (Mar 10) Online decision making (MWU)
Sadly, we do not have time to squeeze in the following topics
- universal hashing and derandomization
- algebraic methods (e.g., polynomial identity testing and matching, network coding)
- compressive sensing
- a taste of learning theory
- smoothed analysis
- spectral sparsification (and randomized linear algebra)
- metric embedding
- discrepancy
- interactive proofs
- entropy and error-correcting codes
- random graphs and sharp thresholds
related material
Similar courses elsewhere (with wonderful lecture notes):
Suggested references:
course description
Instructor: Anna R. Karlin,
CSE 586, tel. 543 9344
Time: Mondays and Wednesdays, 11:30 am - 12:50pm
Office hours: Wednesdays from 7-8pm and by appointment -- contact me privately on edstem or send email.
Teaching assistant: Dorna Abdolazimi
Office hours:
- Thursdays, 5:30-6:30pm
- Also by appointment -- send private message on edstem or send email.
Course evaluation: homework (~80%), project (~20%)
About this course:
Randomization and probabilistic analysis have become fundamental tools
in modern Computer Science,
with applications ranging from combinatorial optimization to machine
learning to cryptography to
complexity theory to the design of protocols for communication
networks. Often randomized algorithms
are more efficient, and conceptually simpler and more elegant than
their deterministic counterparts.
We will cover some of the most widely used techniques for the
analysis of randomized
algorithms and the behavior of random structures from a rigorous
theoretical perspective. A (non-random)
sample of topics that could be covered includes elementary examples like
fingerprinting and minimum cut, large-deviation inequalities, the probabilistic
method, martingales, random graphs,
and the analysis of Markov chains. Tools
from discrete probability will be
illustrated via their application to problems such as randomized rounding,
hashing of high-dimensional data, and
load balancing in distributed systems.